In computability theory, what are examples of decision problems of which it is not known whether they are decidable?
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ My (unpublished) dissertation has an example, see ArXiv 1408.2784 for details. Briefly, given a string representing a hyperidentity (clone equation or restricted second order logic universal equality) and a finite similarity type (set of function symbols), does the logically equivalent infinite set of first order identities have a finite logically equivalent subset? If you restrict the problem by fixing the identity, (e.g. ask just for hyperassociativity and vary the type) the answer is yes, but not uniformly in the hyperidentity. Gerhard "Should Get Back To That" Paseman, 2019.11.06. $\endgroup$– Gerhard PasemanNov 6, 2019 at 16:09
-
5$\begingroup$ There are many ineffective results in number theory that can be converted into an answer to your question. For example, given an elliptic curve defined over $\mathbb Q$, and an integer $r$, is the [rational Mordell-Weil] rank of the elliptic curve equal to $r$? Or how about this: Given a curve of genus at least 2 over $\mathbb Q$ and a list of rational points on the curve, is there any other rational point on the curve? $\endgroup$– Timothy ChowNov 6, 2019 at 19:07
-
8$\begingroup$ This question is nearly a duplicate of a question on cstheory.stackexchange.com. (Joseph O'Rourke mentions this fact in his answer below, but it seems worth putting a comment here at the top of the page.) $\endgroup$– Timothy ChowNov 7, 2019 at 15:53
Add a comment
|
9 Answers
$\begingroup$
$\endgroup$
An integer linear recurrence sequence is a sequence $x_0, x_1, x_2, \ldots$ of integers that obeys a linear recurrence relation $$x_n = a_1 x_{n-1} + a_2 x_{n-2} + \cdots + a_d x_{n-d}$$ for some integer $d\ge 1$, some integer coefficients $a_1, \ldots, a_d$, and all $n\ge d$. The following problem is sometimes known as "Skolem's problem":
Given $d$, $a_1, \ldots, a_d$, $x_0, \ldots x_{d-1}$, does there exist $n$ such that $x_n=0$ ?
It is unknown whether the above problem is undecidable. For more information, see Terry Tao's blog post on the subject.
$\begingroup$
$\endgroup$
13
In Conway's Game of Life, the problem of deciding whether a given pattern with finitely many live cells is a Garden of Eden (i.e. whether it lacks a predecessor).
The main obstacle is that there could be a pattern which has finitely many live cells and a predecessor, but such that all of its predecessors have infinitely many live cells. If we knew there were no such patterns then the problem would be decidable.
Added 2019 December 3: Having learnt about the problem from this post, Ville Salo and Ilkka Törmä have produced a paper ("Gardens of Eden in the Game of Life") showing that this problem is decidable. Interestingly, they don't proceed via the method I suggested here. It remains an open problem to determine if there is a non-Garden-of-Eden pattern with finitely many live cells all of whose predecessors have infinitely many live cells.
Added 2022 January 18: In fact it is false that a finite pattern without finite predecessors must necessarily be a Garden of Eden. This result is also due to Salo and Törmä.
-
1$\begingroup$ Is your last sentence supposed to be easy to see? Suppose I could prove that every pattern with a predecessor has a predecessor with finitely many cells. How would the Garden of Eden algorithm go? Naively I would try exhaustively searching all possible predecessor patterns. This would uncover a predecessor if a predecessor exists, but if a predecessor does not exist, then how do I know when to stop and declare that no predecessor exists? $\endgroup$ Nov 6, 2019 at 21:06
-
2$\begingroup$ @TimothyChow As Ville Salo said, by compactness a Garden of Eden must contain an "orphan", a finite set of cells whose states cannot be achieved no matter how the other cells are filled in. Orphans are decidable because one can check all possible assignments to the cells in the neighbourhoods of the orphan's cells. So one would decide a Garden of Eden by alternatingly trying to find a predecessor and trying to prove that an $n\times n$ box around the pattern gave an orphan. $\endgroup$ Nov 7, 2019 at 6:02
-
1$\begingroup$ @VilleSalo That is indeed the obvious proof strategy, but nobody yet has found a "playing around" scheme that always works. I'm afraid there's no reference. $\endgroup$ Nov 7, 2019 at 6:06
-
9$\begingroup$ This nice problem was screaming to be solved. After obsessing about this for a few days, I found Ilkka Törmä obsessing about it across the corridor. We wrote a paper about it arxiv.org/abs/1912.00692 $\endgroup$ Dec 3, 2019 at 5:19
-
2$\begingroup$ @VilleSalo Nice work! I'm still digesting your paper, but I noticed that the first two parts of your Question 1 "Does every finite-support configuration in the image of the Game of Life have a finite-support preimage? A co-finite-support preimage?" can be proved equivalent, because you can convert between the two kinds of preimage using a construction like the pattern shown in this post. Also I noticed a typo in Lemma 1; $R$ is used before it's defined. $\endgroup$ Dec 3, 2019 at 9:53
$\begingroup$
(Image from Wikipedia.)
$\endgroup$
3
In response to this CompSciTheory (cstheory) question, A simple problem whose decidability is not known , I posted that:
It is unknown whether or not it is decidable to determine if a given shape can tile the plane,
referring to an earlier cstheory question. This is even open for polyomino tiles.
(Image from Wikipedia.)
-
11$\begingroup$ I think this is known to be decidable now, see Siddhartha Bhattacharya, Periodicity and decidability of tilings of Z^2, arxiv.org/abs/1602.05738, which is published now in the American Journal of Mathematics. $\endgroup$ Nov 7, 2019 at 8:23
-
3$\begingroup$ @JeremiasEpperlein: Thanks; I was unaware of this paper. Abstract: "As a consequence, the problem whether a given finite set $F$ tiles $\mathbb{Z^2}$ is decidable." Curiously he does not state this in the body of the paper, only: "Corollary 1.2. The problem whether a given finite set $F$ tiles $\mathbb{Z^2}$ by translations is decidable." $\endgroup$ Nov 7, 2019 at 11:58
-
8$\begingroup$ @Rourke I see, if you allow rotations of the tiles then I think the problem is still open. I am also not sure about tilings of $\mathbb{R}^2$ in contrast to $\mathbb{Z}^2$. $\endgroup$ Nov 7, 2019 at 13:25
$\begingroup$
$\endgroup$
7
The word problem for a finitely presented group $G = \langle A \mid R \rangle $ and the associated canonical homomorphism $\pi : F_A \to G$, asks: given an element $w \in F_A$, do we have $\pi(w) = 1$? There exists finitely presented groups in which the word problem is undecidable, a result independently due to Novikov and Boone.
However, W. Magnus showed that for one-relator groups, i.e. groups $G = \langle A \mid w= 1 \rangle$ with a single defining relation, the word problem is always decidable (though the time-complexity of this solution remains unknown in general as far as I am aware).
The following natural problem, however, remains open:
Is the word problem always decidable for two-relator groups $G = \langle A \mid w_1 = 1, w_2 = 1 \rangle$?
This appears in the Kourovka Notebook as Problem 9.29.
There are also concrete examples of groups for which we do not know whether their word problem is decidable or not. For example, we know very little about how to solve the word problem in most Artin groups. The following is an open problem which appears in the previous link:
Let $G = \langle a, b, c, d \mid aba=bab, ad = da, bdb = dbd, aca = cac, bcb = cbc, cdc = dcd\rangle$.
Is the word problem for $G$ decidable?
It is somewhat surprising that this problem is open -- if one considers the semigroup presentation with the same generators and the same defining relations, then the word problem (appropriately phrased as the problem of comparing two words) is easily solvable!
-
1$\begingroup$ That's a really nice answer, and surprising, thanks Carl-Fredrik! $\endgroup$ Nov 8, 2019 at 14:00
-
1$\begingroup$ @DominicvanderZypen Thank you -- it is indeed surprising. A closely related problem you may be interested in is the fact that the word problem for one-relation semigroups $\langle A \mid u = v \rangle$ remains a long-standing open problem. $\endgroup$ Nov 8, 2019 at 19:39
-
1$\begingroup$ @DominicvanderZypen The word problem goes back to Dehn in the early 1910s, but Adjan in the 1960s looked a great deal at one-relation semigroups in particular, reducing it to a number of cases (and also solving the word problem for one-relator semigroups $\langle A \mid u = 1 \rangle$). $\endgroup$ Nov 9, 2019 at 7:23
-
2$\begingroup$ Wow, you wrote this entire answer without mentioning B. B. Newman! Amazing! $\endgroup$– Asaf Karagila ♦Nov 9, 2019 at 14:32
-
3$\begingroup$ @AsafKaragila Another decision problem which remains open is the conjugacy problem for torsion-free one-relator groups. The conjugacy problem is the problem of deciding whether two given elements are conjugate or not -- it is clearly at least as hard as the word problem. It was solved in 1968 for one-relator groups with torsion by... $\endgroup$ Nov 10, 2019 at 10:39
$\begingroup$
$\endgroup$
One problem about decidability that continues to attract a lot of attention is extensions of Hilbert's 10th problem to other rings of number-theoretic interest, especially the rationals $\mathbb{Q}$. See for instance this nice survey paper of Poonen.
$\begingroup$
$\endgroup$
7
$k$-Piece Dissection is not known to be decidable. Given two polygons and an integer $k$, is there a dissection of the first polygon into k pieces that can be reassembled into the second one?
-
$\begingroup$ It is not clear to me what the problem they ask is. Do I interpret correctly that it is open whether, given two rational polygons of equal area in $\mathbb{R}^2$, it is decidable whether there is a common dissection? $\endgroup$ Dec 3, 2019 at 8:50
-
$\begingroup$ @VilleSalo : I had the same question. I have not asked the authors, but I assume that that is what they meant. $\endgroup$ Dec 3, 2019 at 15:51
-
$\begingroup$ @VilleSalo I noticed today that in Section 9 of the paper, the authors write, "Our proofs remain valid when the input polygons are restricted to be simple (hole-free) and orthogonal with all edges having integer length." They also write, "Is k-Piece Dissection in NP, or even decidable? We do not know the answer to this question even when only orthogonal cuts are allowed and rotations and reflections are forbidden." $\endgroup$ Sep 26, 2023 at 23:03
-
$\begingroup$ Ok, but "integer length edges" still allows uncountably many polygons. $\endgroup$ Sep 27, 2023 at 6:25
-
$\begingroup$ Concretely (and I apologize for this triviality): Suppose the polygons are given by Turing machines telling you better and better precision on the angles and positions of edges (I mean, how else, when no specific type of algebraicity is specified?) Consider two unit cubes that have been slightly distorted (still with unit sides) by pushing two corners together. You can never know if two such polygons are the same (and it's easy to arrange that they have no common $k$-dissection for any $k$ when distinct). $\endgroup$ Sep 27, 2023 at 6:32
$\begingroup$
$\endgroup$
0
Perhaps the biggest open problem in symbolic dynamics is the equivalence problem for subshifts of finite type.
Given a finite alphabet $\mathcal{A}$ and a finite set $\mathcal{F}$ of finite words over $\mathcal{A}$ (the forbidden words), the corresponding subshift of finite type consists of
The space $S\subseteq \mathcal{A}^\mathbb{Z}$ of all bi-infinite words over $\mathcal{A}$ that do not have any of the forbidden words as subwords, and
The shift map $\sigma \colon S\to S$ that shifts each symbol to the left one spot.
Two subshifts $(S,\sigma)$ and $(S',\sigma')$ of finite type are equivalent if they are conjugate as dynamical systems, i.e. if there exists a homeomorphism $h\colon S\to S'$ such that $h\circ \sigma = \sigma'\circ h$.
Is there an algorithm to determine whether two subshifts of finite type $(S,\sigma)$ and $(S',\sigma')$ are equivalent?
See M. Boyle, Open problems in symbolic dynamics. Contemporary mathematics 469 (2008): 69-118.
A solution to this problem was famously published in the Annals of Mathematics by R. F. Williams in a 1973 paper. An error was found in his proof, so the correctness of his main classification algorithm became the "Williams conjecture". This conjecture was disproven by K. H. Kim and F. W. Roush in 1990's in a series of two papers, and at present we have essentially no idea whether equivalence is decidable.
$\begingroup$
$\endgroup$
It remains open whether the won-position problem of infinite chess is decidable, the problem of determining whether a given finite position in infinite chess is winning for white or not. See Richard Stanley's question at https://mathoverflow.net/q/27967. Meanwhile, the mate-in-$n$ problem of infinite chess is decidable, and so the open part of the problem necessarily concerns positions with infinite game value.
Also open is the optimal-play problem: given a won position, is a given move optimal?
$\begingroup$
$\endgroup$
Inspired by a previous (now deleted) post:
We do not know if every even natural number (at least four) is a sum of two primes [Goldbach, 1742]. However, there is a simple algorithm that decides if a given even number (at least four) is a sum of two primes.
Similarly but differently, we do not know if every even natural number is a difference of two primes [Maillet, 1905]. Here there is no (known) algorithm that decides if a given even number is a difference of two primes.
These are the examples given in Gödel, Escher, Bach to teach the reader about the difference between bounded and unbounded search.
After a few searches, ending here, I found that there are more difficult, and earlier, versions of Maillet's question. Kronecker [1901] asks if every even natural number is the difference of two primes in infinitely many ways. Polignac [1849] asks if every even natural number is the difference of infinitely many pairs of consecutive primes. These two conjectures have their related decision problems. However, now the unbounded search is much worse...