23
$\begingroup$

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

$\endgroup$
  • 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 Paseman Nov 6 at 16:09
  • 4
    $\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 Chow Nov 6 at 19:07
  • 6
    $\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 Chow Nov 7 at 15:53
31
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
  • 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$ – Timothy Chow Nov 6 at 21:06
  • $\begingroup$ Timothy Chow: by compactness a finite subpattern has no preimage. CA are continuous in Cantor topology. $\endgroup$ – Ville Salo Nov 6 at 21:27
  • 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$ – Oscar Cunningham Nov 7 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$ – Oscar Cunningham Nov 7 at 6:06
  • 1
    $\begingroup$ @TLW You try all values of $n$ increasingly. For each $n\times n$ box centred on the pattern you try to find a predecessor of the pattern all of whose live cells are in the box, and if that doesn't work you try to prove the box is an orphan. If neither of these succeeds then you increase $n$ and try again. Eventually you must succeed one way or the other since if the pattern has a predecessor it has a predecessor with finitely many live cells (which your box will eventually contain), and if it doesn't then it has an orphan (which your box will eventually contain). $\endgroup$ – Oscar Cunningham Nov 8 at 9:25
15
$\begingroup$

This is a very broad question and might be closed for that reason.

Anyways, 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.

$\endgroup$
15
$\begingroup$

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.


          Tiling
          (Image from Wikipedia.)


$\endgroup$
  • 6
    $\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$ – Jeremias Epperlein Nov 7 at 8:23
  • 1
    $\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$ – Joseph O'Rourke Nov 7 at 11:58
  • 5
    $\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$ – Jeremias Epperlein Nov 7 at 13:25
14
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ That's a really nice answer, and surprising, thanks Carl-Fredrik! $\endgroup$ – Dominic van der Zypen Nov 8 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$ – Carl-Fredrik Nyberg Brodda Nov 8 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$ – Carl-Fredrik Nyberg Brodda Nov 9 at 7:23
  • 1
    $\begingroup$ Wow, you wrote this entire answer without mentioning B. B. Newman! Amazing! $\endgroup$ – Asaf Karagila Nov 9 at 14:32
  • 1
    $\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$ – Carl-Fredrik Nyberg Brodda Nov 10 at 10:39
11
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.