# Decision problems for which it is unknown whether they are decidable

In computability theory, what are examples of decision problems of which it is not known whether they are decidable?

• 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. Nov 6 '19 at 16:09
• 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? Nov 6 '19 at 19:07
• 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.) Nov 7 '19 at 15:53

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.

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.

• 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? Nov 6 '19 at 21:06
• @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. Nov 7 '19 at 6:02
• @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. Nov 7 '19 at 6:06
• 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 Dec 3 '19 at 5:19
• @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. Dec 3 '19 at 9:53

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.)

• 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. Nov 7 '19 at 8:23
• @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." Nov 7 '19 at 11:58
• @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$. Nov 7 '19 at 13:25

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.

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!

• That's a really nice answer, and surprising, thanks Carl-Fredrik! Nov 8 '19 at 14:00
• @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. Nov 8 '19 at 19:39
• @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$). Nov 9 '19 at 7:23
• Wow, you wrote this entire answer without mentioning B. B. Newman! Amazing! Nov 9 '19 at 14:32
• @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... Nov 10 '19 at 10:39

$$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?

• 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? Dec 3 '19 at 8:50
• @VilleSalo : I had the same question. I have not asked the authors, but I assume that that is what they meant. Dec 3 '19 at 15:51

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?

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.