<p>UPDATE: The problem I mentioned here is now known to be undecidable! <a href="http://arxiv.org/abs/1605.05274">http://arxiv.org/abs/1605.05274</a>  Moreover, the paper was inspired by reading this very answer. :)</p>

<hr>

<p>Programmers in your math-major audience may be surprised to learn that the question "is this type implicitly convertible to that type?" is not known to be decidable in any of Java 5, C# 4 and Scala 2.</p>

<p>For more details, see Andrew Kennedy and Benjamin Pierce's paper <a href="http://repository.upenn.edu/cis_papers/671/">"On Decidability of Nominal Subtyping with Variance"</a>. The paper gives some examples of additional restrictions to the type systems of these languages, under which nominal subtyping becomes known to be decidable or known to be undecidable.</p>

<p>Interestingly, the paper was written well before generic covariance and contravariance were added to C#, but the authors correctly anticipated the direction the language was heading. (This is unsurprising; the authors designed the underlying support for variance in the CLR that I took advantage of when adding variance to C#! They did the heavy lifting.)</p>

CC BY-SA 4.0
2019-11-08T23:10:26.417Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/100835/discussion-on-answer-by-eric-lippert-a-simple-decision-problem-whose-decidabilit).
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2013-09-04T21:29:52.827Z
2016-05-26T16:12:58.037Z
2016-05-26T16:12:58.037Z
Eric Lippert
<p>Hilbert's tenth problem over rationals: "Does this polynomial equation have a rational solution?"</p>

CC BY-SA 3.0
2013-09-04T17:42:37.803Z
Thanks - do you have a link to someplace that says it's open?
Lev Reyzin
CC BY-SA 3.0
2013-09-04T21:20:36.380Z
See http://www-math.mit.edu/~poonen/papers/subrings.pdf (second paragraph). There is also an expository article at http://www-math.mit.edu/~poonen/papers/aws2003.pdf
Boris Bukh
CC BY-SA 3.0
2013-09-06T05:24:33.727Z
it would also be helpful to see a sketch/outline description of why this problem is not equivalent to Hilberts 10th problem & the same proof does not apply.
vzn
CC BY-SA 3.0
2013-09-06T11:45:39.083Z
vzn: Equations over rationals can be seen as a special case of equations over integers (by multiplying to clear the denominators).  So the question is whether that special case of Hilbert's 10th problem is already undecidable.  The Diophantine equations produced by the existing proofs don't have the special form required.
Scott Aaronson
CC BY-SA 3.0
2013-09-19T17:22:06.933Z
right. figured that. a detail/synopsis of "why they dont have the special form required" from the (more TCS, less math) pov of the natural-to-try reduction would be helpful. apparently its a subtle issue.
vzn
CC BY-SA 3.0
2013-09-26T21:31:24.010Z
@vzn One reason that it is subtle is that most (perhaps all) proof strategies would violate Mazur's Conjecture. See page 1 of Boris Bukh's first link for more.
David E Speyer
CC BY-SA 3.0
2013-09-04T03:46:22.337Z
2013-09-04T03:46:22.337Z
Boris Bukh
<p>The problem of given a linear recurrence along with its initial values, does it take the value 0?</p>

<p>Two reference:</p>

<p><a href="http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/">http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/</a></p>

<p><a href="http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf">http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf</a></p>

CC BY-SA 3.0
2015-10-13T07:17:50.127Z
Now on Wikipedia: https://en.wikipedia.org/wiki/Skolem_problem
David Eppstein
CC BY-SA 3.0
2013-09-04T13:21:10.723Z
2013-09-04T13:21:10.723Z
Magnus Find
<p>A simple problem whose decidability is unknown is the following (I think it is still open):</p>

<p><strong>Infinite chess</strong>:</p>

<p><strong>Input</strong>: A finite list of chess pieces and their starting positions on a $Z \times Z$ chessboard;<br>
<strong>Question</strong>: Can White force mate?</p>

<p>If we add the constraint that White must mate in $n$ moves ($n$ is part of the input), then it becomes decidable:
see <a href="http://arxiv.org/pdf/1201.5597v4" rel="noreferrer">Dan Brumleve, Joel David Hamkins, and Philipp Schlicht, The mate-in-n problem of infinite chess is decidable</a>.</p>

<p><br>
Another simple problem is the behaviour of <a href="http://en.wikipedia.org/wiki/Langton%27s_ant" rel="noreferrer">Langton's ant</a> on finite initial configuration.</p>

<p><strong>Langton's ant behaviour with finite support</strong>:</p>

<p>Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to the rules below:</p>

<ul>
<li>At a white square, turn 90° right, flip the color of the square, move forward one unit</li>
<li>At a black square, turn 90° left, flip the color of the square, move forward one unit</li>
</ul>

<p><strong>Input</strong>: a finite configuration (black/white) of the plane and the ant position;<br>
<strong>Question</strong>: Does the ant always end building a recurrent infinite "highway"?</p>

<p><img src="https://i.sstatic.net/SFPcA.jpg" alt="enter image description here"></p>

<p>For infinite support the problem is undecidable, see: 
<a href="http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf" rel="noreferrer">A. Gajardo, A. Moreira and E. Goles, Complexity of Langton’s ant</a></p>

CC BY-SA 3.0
2013-09-04T06:55:28.723Z
2016-05-31T11:04:05.060Z
2016-05-31T11:04:05.060Z
Marzio De Biasi
<p>Collatz Problem is simple-to-describe problem whose decidability is open. It involves a simple recurrence of elementary arithmetic operations. </p>

<blockquote>
  <p>$f(n)=\mathsf{\{}$ $n/2$ for even integer,  $3n+1$ for odd integer</p>
</blockquote>

<p>The problem is deciding whether iterating this function always return to 1 for a given positive integer $n_0$.</p>

<p>Interestingly, a generalization of the Collatz problem was shown to be undecidable.</p>

<p>References:</p>

<p>1- <a href="http://math.mit.edu/~poonen/papers/sampler.pdf">UNDECIDABLE PROBLEMS: A SAMPLER</a>, BJORN POONEN</p>

<p>2- <a href="http://mathworld.wolfram.com/CollatzProblem.html">Weisstein, Eric W. "Collatz Problem."</a> From MathWorld--A Wolfram Web Resource.</p>

<p>3- <a href="http://www.ams.org/bookstore/pspdf/mbk-78-prev.pdf">The 3X+1 Problem: An Overview</a>, Jeffrey C. Lagarias</p>

CC BY-SA 3.0
2013-09-14T14:29:32.933Z
study of Collatz conjecture from a more [TCS/empirical angle with many refs here](http://vzn1.wordpress.com/code/collatz-conjecture-experiments/) (eg via [FSM transducer recursion](http://en.wikipedia.org/wiki/Finite_state_transducer), [tag system](http://en.wikipedia.org/wiki/Tag_system) etc)
vzn
CC BY-SA 3.0
2013-09-06T08:41:50.077Z
2013-09-07T05:53:12.013Z
2013-09-07T05:53:12.013Z
Mohammad Al-Turkistany
<p>It is unknown whether or not
<a href="https://cstheory.stackexchange.com/q/32538/337">it is decidable to determine if a given shape can tile the plane</a>,
even for polyomino tiles.</p>

<p><hr />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
<a href="https://i.sstatic.net/284oP.jpg" rel="noreferrer"><img src="https://i.sstatic.net/284oP.jpg" alt="Tiling"></a>
<br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
<sup>
(Image from <a href="https://en.wikipedia.org/wiki/Polyomino#Tiling_the_plane_with_copies_of_a_single_polyomino" rel="noreferrer">Wikipedia</a>.)
</sup></p>

<hr />

CC BY-SA 4.0
2020-12-27T06:24:23.060Z
I am 5 years late to ask, but for those unfamiliar with the area, how is the shape given in a finitary way as input?
Caleb Stanford
CC BY-SA 4.0
2020-12-27T12:11:36.593Z
@6005: Just as either a list of vertices, or as a list of edge lengths and $\pm$ for turns. The latter is likely the most useful.
Joseph O'Rourke
CC BY-SA 4.0
2015-10-12T23:46:17.257Z
2019-11-07T17:11:56.583Z
2019-11-07T17:11:56.583Z
Joseph O'Rourke
<p>The decidability of <em>conjunctive query containment</em> has been open for over twenty years.  Resolving this would be a breakthrough in database theory.</p>

<p><em>Query containment</em> takes as input two queries $Q_1$ and $Q_2$ and asks whether $Q_1$ applied to <em>any</em> database $I$ yields at least as many answers as $Q_2$ when applied to the same database $I$.</p>

<p>In <em>conjunctive</em> queries one uses AND to link together existentially quantified predicates.  In SQL terms, conjunctive queries are the SELECT-FROM-WHERE queries using "=" and "AND" but no subqueries or aggregation.  This is perhaps the most common kind of database query, and includes most search engine queries.</p>

<p>What makes query containment potentially undecidable is the quantification over infinitely many possible databases $I$.  Algorithms that do exist tend to rely on turning this infinite quantification into a syntactic question, whether there is a homomorphism of some kind between $Q_1$ and $Q_2$.</p>

<p>For slightly more powerful (i.e. "advanced") queries that allow OR or $\ne$, query containment is known to be undecidable.</p>

<p>To compare queries by counting how many answers they generate, one uses the semiring $(N,+,\times)$ of natural numbers with addition and multiplication.  Query containment can also be generalized to other ordered semirings.  For all positive semirings, conjunctive query containment is NP-hard.  However, for most semirings other than $(N,+,\times)$ that people care about, conjunctive query containment is decidable.  Unfortunately, the counting case falls into the zone of semirings where decidability of conjunctive query containment is still open.</p>

<p>For pointers to the extensive literature and a rigorous treatment, see a ToDS paper (in press) by some people.</p>

<p>One could turn this into a compelling question for a non-technical audience by demonstrating <a href="http://www.googlefight.com/">Googlefight</a>, then asking how one can tell which query gives more answers than the other, without first peeking at the data.  If $Q$ and $R$ are conjunctive queries, then $Q$ always gives at least as many answers as $Q \text{ AND } R$, because the latter is somehow syntactically "larger" (there is a homomorphism from $Q$ to it), but things get rather tricky from there on.</p>

CC BY-SA 3.0
2013-09-05T14:11:34.143Z
Here's a [related article](http://homepages.inf.ed.ac.uk/ekostyle/TODS-2012-0083.pdf).
Martin Berger
CC BY-SA 3.0
2014-02-17T18:40:06.980Z
@MartinBerger: The ToDS version includes the NP-hardness proof mentioned above, has full proofs, and is open access (though omits the material about unions of CQs due to lack of space).  http://dx.doi.org/10.1145/2556524
András Salamon
CC BY-SA 3.0
2013-09-04T22:00:41.467Z
2013-09-05T16:04:06.277Z
2013-09-05T16:04:06.277Z
András Salamon
<p><a href="http://en.wikipedia.org/wiki/Post_correspondence_problem#Variants">Post's Correspondence problem</a> with a fixed number of tiles of between 3 and 6. </p>

<p>While it is not really simple to describe, it does have a very "playful" description, and I find it suitable for intuition-level talks.</p>

CC BY-SA 3.0
2013-09-04T03:48:03.310Z
2013-09-04T03:48:03.310Z
Shaull
<p>The Generalized star-height problem : "how many nesting of Kleene stars do I need to represent this regular language, with a regular expression with complementation allowed ?"</p>

<p>We don't even know if the algorithm that always returns 1 (except 0 for star-free languages, which is a decidable case) is correct.</p>

CC BY-SA 3.0
2013-09-04T10:12:10.403Z
2013-09-04T10:12:10.403Z
Denis
<p>A problem from Automata Theory.</p>

<p><strong>Input:</strong> A DFA $D$ over a binary input alphabet.</p>

<p><strong>Question:</strong> Does there exist a bit string $x$ such that $D$ accepts $x$ and $x$ represents a prime number in binary?  In other words, is $L(D) \cap Primes$ non-empty?</p>

<p><strong>Comments:</strong> I originally heard this problem from a stackexchange answer by Jeffrey Shallit.  If you know of any references to it, please let me know.  Thank you!</p>

<p><strong>Related Posts:</strong></p>

<p>(1) <a href="https://cstheory.stackexchange.com/questions/22493/are-there-any-open-problems-left-about-dfas/22503#22503">Are there any open problems left about DFAs?</a></p>

<p>(2) <a href="https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime">https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime</a></p>

<p><strong>Related Work:</strong> <a href="https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf" rel="nofollow noreferrer">https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf</a></p>

<p>"Minimal Elements for the Prime Numbers" by C. Bright, R. Devillers, and J. Shallit</p>

CC BY-SA 3.0
2015-10-04T05:31:47.827Z
2015-10-14T01:43:26.787Z
2017-04-13T12:48:30.830Z
Michael Wehar
<p><strong>Iterated maps on the interval (description from <a href="http://perso.ens-lyon.fr/pascal.koiran/problems.html">here</a>):</strong></p>

<p>(very related to the problem proposed by Magnus Find) </p>

<p>Let $F$ be a piecewise-linear map on the unit interval and $x$ a point in this interval.
We consider the sequence of iterates starting from $x$: $x$, $F(x)$, $F(F(x))$, and so on.
Given $F$ and $x$, does this sequence reach a fixed point of $F$?</p>

<p>Decidability is also unknown for the reachability variant: given $F$ and $x$, and $y$, does the sequence starting from $x$ reach $y$ in a finite number of iterations?</p>

<p>It is open even when $F$ has only two linear pieces.</p>

<p>Remark: for this problem to make sense, $F$ and $x$ (and $y$) must have a finite description.
We assume here that $x$ is rational, and that the slopes and breakpoints of $F$ are also rational.</p>

<p>A reference: <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.7864">Asarin 2011</a>. </p>

CC BY-SA 3.0
2015-01-09T12:18:23.423Z
2015-01-09T12:44:38.860Z
2015-01-09T12:44:38.860Z
Nicolas Perrin
<p>there seems to be a fairly natural way/angle to study this question that is utilized in at least 3 papers as follows. </p>

<p>let $TM(k,l)$ be the set of Turing Machine with $k$ states and $l$ symbols. for low/small $k,l$ the machines are provably decidable, for larger $k,l$ past some threshhold they are provably undecidable. however in the intermediate region, they are not consistently known to be either decidable or undecidable (and the full table is presumably unknowable based on the same undecidability phenomena of the halting problem). </p>

<p>the results can be displayed on a grid as in some of the following refs. also in the intermediate region it is actually known that some (unresolved) machines are capable of simulating the Collatz conjecture for some inputs.</p>

<p>therefore there is clearly a <a href="http://www.cse.unsw.edu.au/~tw/phase.ppt" rel="nofollow">"transition-point"</a> like phenomena operating here but not within a computable region but in an unusual sense of between computable and uncomputable.</p>

<ul>
<li><p><a href="http://www.dm.unito.it/~cerruti/ac/paperpm1.pdf" rel="nofollow">Small Turing machines
and generalized busy beaver competition</a> Michel</p></li>
<li><p><a href="http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf" rel="nofollow">The complexity of small universal Turing
machines: a survey</a> Woods, Neary</p></li>
<li><p><a href="http://arxiv.org/abs/0906.3329" rel="nofollow">On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results</a> De Mol</p></li>
</ul>

CC BY-SA 3.0
2013-09-09T18:41:43.923Z
2013-09-09T18:41:43.923Z
vzn
<p><a href="http://en.wikipedia.org/wiki/Cellular_automaton" rel="nofollow">cellular automata</a>, very simple computing devices, have various open questions about undecidability. some of the standard Wolfram CAs are conjectured to be universal (although a simple list of those conjectured undecidable does not seem to be available). in particular CA <a href="http://mathworld.wolfram.com/Rule54.html" rel="nofollow">Rule 54</a> is conjectured by Wolfram to be Turing-complete. there are only $2^8$ basic CAs which most are now resolved as not Turing complete, but at least one was relatively recently found to be Turing complete, <a href="http://en.wikipedia.org/wiki/Rule_110" rel="nofollow">rule 110</a>, in a remarkable proof by Cook, using the CA to emulate a Turing-complete <a href="http://en.wikipedia.org/wiki/Tag_systems" rel="nofollow">tag system</a>.</p>

<p>also as an example of a "near miss", or "open question relatively recently resolved as TM complete", the <a href="http://www.wolframscience.com/prizes/tm23/index.html" rel="nofollow">Wolfram 2,3 machine was proved universal in 2007 for a $25K prize</a>. the contest was announced in May 2007 and the contest <a href="http://www.wolframscience.com/prizes/tm23/solved.html" rel="nofollow">announced the winner Smith in October 2007</a>.</p>

CC BY-SA 3.0
2013-09-05T15:30:57.943Z
2013-09-05T15:42:31.137Z
2013-09-05T15:42:31.137Z
vzn
<p>there is a fairly natural way to map most open problems onto questions of (un)decidability. most open problems generally are not known to be provable or unprovable.</p>

<p>on the web there is some informal confusion about the undecidability of the <a href="http://en.wikipedia.org/wiki/P_vs_np" rel="nofollow">P vs NP</a> problem, which is not strictly a decision problem, therefore to talk about its undecidability is not technically correct. but on the other hand there does seem to be a close/natural link between undecidability and provability as follows. </p>

<p>for example consider </p>

<blockquote>
  <p>the language $L$ of binary strings where a string/integer $x$ is in the language iff there exists a $O(n^x)$ DTime TM that solves an NP complete problem </p>
</blockquote>

<p>is this language decidable? that is an question about a language with its decidability open that is basically closely tied (even, virtually identical) to the P vs NP problem and its inherent (un?)provability.</p>

<p>as for P vs NP as "simple to describe", it only requires concepts of <a href="http://en.wikipedia.org/wiki/Turing_machine" rel="nofollow">TMs</a>, <a href="http://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow">Big O runtime notation</a>, <a href="http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine" rel="nofollow">nondeterminism</a> which are a fairly simple (some of the most basic concepts of TCS) and taught at the undergraduate level or which a gifted high school student could understand. </p>

<p>in fact NP vs P/Poly is also open, and can be mapped onto an open question about decidability in the same way, and this can be stated as a fairly simple problem about the growth of minimal (monotone?) circuits to recognize NP complete problems (eg cliques).</p>

CC BY-SA 4.0
2019-11-07T22:58:38.050Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/100805/discussion-on-answer-by-vzn-a-simple-decision-problem-whose-decidability-is-not).
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2013-09-04T16:56:01.000Z
2013-09-04T16:56:01.000Z
vzn
<p>The <a href="http://uniformlyatrandom.wordpress.com/2009/07/09/matrix-mortality/">Matrix Mortality Problem</a> for 2x2 matrices.  I.e., given a finite list of 2x2 integer matrices M<sub>1</sub>,...,M<sub>k</sub>, can the M<sub>i</sub>'s be multiplied in any order (with arbitrarily many repetitions) to produce the all-0 matrix?</p>

<p>(The 3x3 case is known to be undecidable.  The 1x1 case, of course, is decidable.)</p>

CC BY-SA 3.0
2017-01-18T19:07:29.270Z
http://epubs.siam.org/doi/abs/10.1137/1.9781611974782.12 Igor Potapov and Pavel Semukhin recently showed this is decidable.
Chao Xu
CC BY-SA 3.0
2017-09-07T06:04:27.317Z
@RickyDemer You are correct, my mistake.
Chao Xu
CC BY-SA 3.0
2013-09-04T23:12:32.233Z
2013-09-04T23:17:45.777Z
2013-09-04T23:17:45.777Z
Scott Aaronson
<p>I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability.  I want to give an example of a problem that we do not currently know to be decidable or undecidable.  There are many such problems, but none seem to stand out as nice examples so far.</p>

<p><strong>What is a simple-to-describe <a href="https://en.m.wikipedia.org/wiki/Decision_problem" rel="noreferrer">decision problem</a> whose decidability is open?</strong></p>

CC BY-SA 4.0
2019-11-07T22:55:24.617Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/100804/discussion-on-question-by-lev-reyzin-a-simple-decision-problem-whose-decidabilit).
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2021-07-04T18:56:44.060Z
Related: [Decision problems for which it is unknown whether they are decidable](https://mathoverflow.net/q/345388).
Timothy Chow
<computability><decidability>
A simple decision problem whose decidability is not known
Lev Reyzin
# A simple decision problem whose decidability is not known

(Asked by: username_0 on 2013-09-04)

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not currently know to be decidable or undecidable. There are many such problems, but none seem to stand out as nice examples so far.

**What is a simple-to-describe [decision problem](https://en.m.wikipedia.org/wiki/Decision_problem) whose decidability is open?**

**Tags:** computability, decidability

> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/100804/discussion-on-question-by-lev-reyzin-a-simple-decision-problem-whose-decidabilit).  
> **username_2**: Related: [Decision problems for which it is unknown whether they are decidable](https://mathoverflow.net/q/345388).  

---

## 15 answers

### Answer by username_6 on 2013-09-04. Score: 108 | Accepted answer

The [Matrix Mortality Problem](http://uniformlyatrandom.wordpress.com/2009/07/09/matrix-mortality/) for 2x2 matrices. I.e., given a finite list of 2x2 integer matrices M1,...,Mk, can the Mi's be multiplied in any order (with arbitrarily many repetitions) to produce the all-0 matrix?

(The 3x3 case is known to be undecidable. The 1x1 case, of course, is decidable.)

> **Comments:**
> **username_20**: http://epubs.siam.org/doi/abs/10.1137/1.9781611974782.12 Igor Potapov and Pavel Semukhin recently showed this is decidable.  
> **username_20**: @RickyDemer You are correct, my mistake.  

---

### Answer by username_3 on 2013-09-04. Score: 67

UPDATE: The problem I mentioned here is now known to be undecidable! <http://arxiv.org/abs/1605.05274> Moreover, the paper was inspired by reading this very answer. :)

---

Programmers in your math-major audience may be surprised to learn that the question "is this type implicitly convertible to that type?" is not known to be decidable in any of Java 5, C# 4 and Scala 2.

For more details, see Andrew Kennedy and Benjamin Pierce's paper ["On Decidability of Nominal Subtyping with Variance"](http://repository.upenn.edu/cis_papers/671/). The paper gives some examples of additional restrictions to the type systems of these languages, under which nominal subtyping becomes known to be decidable or known to be undecidable.

Interestingly, the paper was written well before generic covariance and contravariance were added to C#, but the authors correctly anticipated the direction the language was heading. (This is unsurprising; the authors designed the underlying support for variance in the CLR that I took advantage of when adding variance to C#! They did the heavy lifting.)

> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/100835/discussion-on-answer-by-eric-lippert-a-simple-decision-problem-whose-decidabilit).  

---

### Answer by username_4 on 2013-09-04. Score: 57

Hilbert's tenth problem over rationals: "Does this polynomial equation have a rational solution?"

> **Comments:**
> **username_0**: Thanks - do you have a link to someplace that says it's open?  
> **username_4**: See http://www-math.mit.edu/~poonen/papers/subrings.pdf (second paragraph). There is also an expository article at http://www-math.mit.edu/~poonen/papers/aws2003.pdf  
> **username_5**: it would also be helpful to see a sketch/outline description of why this problem is not equivalent to Hilberts 10th problem & the same proof does not apply.  
> **username_6**: username_5: Equations over rationals can be seen as a special case of equations over integers (by multiplying to clear the denominators).  So the question is whether that special case of Hilbert's 10th problem is already undecidable.  The Diophantine equations produced by the existing proofs don't have the special form required.  
> **username_5**: right. figured that. a detail/synopsis of "why they dont have the special form required" from the (more TCS, less math) pov of the natural-to-try reduction would be helpful. apparently its a subtle issue.  
> **username_7**: @username_5 One reason that it is subtle is that most (perhaps all) proof strategies would violate Mazur's Conjecture. See page 1 of username_4's first link for more.  

---

### Answer by username_8 on 2013-09-04. Score: 33

The problem of given a linear recurrence along with its initial values, does it take the value 0?

Two reference:

<http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/>

<http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf>

> **Comments:**
> **username_9**: Now on Wikipedia: https://en.wikipedia.org/wiki/Skolem_problem  

---

### Answer by username_10 on 2013-09-04. Score: 29

A simple problem whose decidability is unknown is the following (I think it is still open):

**Infinite chess**:

**Input**: A finite list of chess pieces and their starting positions on a $Z \times Z$ chessboard;  
**Question**: Can White force mate?

If we add the constraint that White must mate in $n$ moves ($n$ is part of the input), then it becomes decidable:
see [Dan Brumleve, Joel David Hamkins, and Philipp Schlicht, The mate-in-n problem of infinite chess is decidable](http://arxiv.org/pdf/1201.5597v4).

Another simple problem is the behaviour of [Langton's ant](http://en.wikipedia.org/wiki/Langton%27s_ant) on finite initial configuration.

**Langton's ant behaviour with finite support**:

Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to the rules below:

* At a white square, turn 90° right, flip the color of the square, move forward one unit
* At a black square, turn 90° left, flip the color of the square, move forward one unit

**Input**: a finite configuration (black/white) of the plane and the ant position;  
**Question**: Does the ant always end building a recurrent infinite "highway"?

![enter image description here](https://i.sstatic.net/SFPcA.jpg)

For infinite support the problem is undecidable, see:
[A. Gajardo, A. Moreira and E. Goles, Complexity of Langton’s ant](http://www.dim.uchile.cl/~anmoreir/oficial/langton_dam.pdf)


---

### Answer by username_11 on 2013-09-06. Score: 23

Collatz Problem is simple-to-describe problem whose decidability is open. It involves a simple recurrence of elementary arithmetic operations.

> $f(n)=\mathsf{\{}$ $n/2$ for even integer, $3n+1$ for odd integer

The problem is deciding whether iterating this function always return to 1 for a given positive integer $n\_0$.

Interestingly, a generalization of the Collatz problem was shown to be undecidable.

References:

1- [UNDECIDABLE PROBLEMS: A SAMPLER](http://math.mit.edu/~poonen/papers/sampler.pdf), BJORN POONEN

2- [Weisstein, Eric W. "Collatz Problem."](http://mathworld.wolfram.com/CollatzProblem.html) From MathWorld--A Wolfram Web Resource.

3- [The 3X+1 Problem: An Overview](http://www.ams.org/bookstore/pspdf/mbk-78-prev.pdf), Jeffrey C. Lagarias

> **Comments:**
> **username_5**: study of Collatz conjecture from a more [TCS/empirical angle with many refs here](http://username_51.wordpress.com/code/collatz-conjecture-experiments/) (eg via [FSM transducer recursion](http://en.wikipedia.org/wiki/Finite_state_transducer), [tag system](http://en.wikipedia.org/wiki/Tag_system) etc)  

---

### Answer by username_12 on 2015-10-12. Score: 23

It is unknown whether or not
[it is decidable to determine if a given shape can tile the plane](https://cstheory.stackexchange.com/q/32538/337),
even for polyomino tiles.

---

         
[![Tiling](https://i.sstatic.net/284oP.jpg)](https://i.sstatic.net/284oP.jpg)
  
         
(Image from [Wikipedia](https://en.wikipedia.org/wiki/Polyomino#Tiling_the_plane_with_copies_of_a_single_polyomino).)

---

> **Comments:**
> **username_13**: I am 5 years late to ask, but for those unfamiliar with the area, how is the shape given in a finitary way as input?  
> **username_12**: @6005: Just as either a list of vertices, or as a list of edge lengths and $\pm$ for turns. The latter is likely the most useful.  

---

### Answer by username_14 on 2013-09-04. Score: 19

The decidability of *conjunctive query containment* has been open for over twenty years. Resolving this would be a breakthrough in database theory.

*Query containment* takes as input two queries $Q\_1$ and $Q\_2$ and asks whether $Q\_1$ applied to *any* database $I$ yields at least as many answers as $Q\_2$ when applied to the same database $I$.

In *conjunctive* queries one uses AND to link together existentially quantified predicates. In SQL terms, conjunctive queries are the SELECT-FROM-WHERE queries using "=" and "AND" but no subqueries or aggregation. This is perhaps the most common kind of database query, and includes most search engine queries.

What makes query containment potentially undecidable is the quantification over infinitely many possible databases $I$. Algorithms that do exist tend to rely on turning this infinite quantification into a syntactic question, whether there is a homomorphism of some kind between $Q\_1$ and $Q\_2$.

For slightly more powerful (i.e. "advanced") queries that allow OR or $\ne$, query containment is known to be undecidable.

To compare queries by counting how many answers they generate, one uses the semiring $(N,+,\times)$ of natural numbers with addition and multiplication. Query containment can also be generalized to other ordered semirings. For all positive semirings, conjunctive query containment is NP-hard. However, for most semirings other than $(N,+,\times)$ that people care about, conjunctive query containment is decidable. Unfortunately, the counting case falls into the zone of semirings where decidability of conjunctive query containment is still open.

For pointers to the extensive literature and a rigorous treatment, see a ToDS paper (in press) by some people.

One could turn this into a compelling question for a non-technical audience by demonstrating [Googlefight](http://www.googlefight.com/), then asking how one can tell which query gives more answers than the other, without first peeking at the data. If $Q$ and $R$ are conjunctive queries, then $Q$ always gives at least as many answers as $Q \text{ AND } R$, because the latter is somehow syntactically "larger" (there is a homomorphism from $Q$ to it), but things get rather tricky from there on.

> **Comments:**
> **username_15**: Here's a [related article](http://homepages.inf.ed.ac.uk/ekostyle/TODS-2012-0083.pdf).  
> **username_14**: @MartinBerger: The ToDS version includes the NP-hardness proof mentioned above, has full proofs, and is open access (though omits the material about unions of CQs due to lack of space).  http://dx.doi.org/10.1145/2556524  

---

### Answer by username_16 on 2013-09-04. Score: 18

[Post's Correspondence problem](http://en.wikipedia.org/wiki/Post_correspondence_problem#Variants) with a fixed number of tiles of between 3 and 6.

While it is not really simple to describe, it does have a very "playful" description, and I find it suitable for intuition-level talks.


---

### Answer by username_17 on 2013-09-04. Score: 13

The Generalized star-height problem : "how many nesting of Kleene stars do I need to represent this regular language, with a regular expression with complementation allowed ?"

We don't even know if the algorithm that always returns 1 (except 0 for star-free languages, which is a decidable case) is correct.


---

### Answer by username_18 on 2015-10-04. Score: 11

A problem from Automata Theory.

**Input:** A DFA $D$ over a binary input alphabet.

**Question:** Does there exist a bit string $x$ such that $D$ accepts $x$ and $x$ represents a prime number in binary? In other words, is $L(D) \cap Primes$ non-empty?

**Comments:** I originally heard this problem from a stackexchange answer by Jeffrey Shallit. If you know of any references to it, please let me know. Thank you!

**Related Posts:**

(1) [Are there any open problems left about DFAs?](https://cstheory.stackexchange.com/questions/22493/are-there-any-open-problems-left-about-dfas/22503#22503)

(2) <https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime>

**Related Work:** <https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf>

"Minimal Elements for the Prime Numbers" by C. Bright, R. Devillers, and J. Shallit


---

### Answer by username_19 on 2015-01-09. Score: 8

**Iterated maps on the interval (description from [here](http://perso.ens-lyon.fr/pascal.koiran/problems.html)):**

(very related to the problem proposed by username_8)

Let $F$ be a piecewise-linear map on the unit interval and $x$ a point in this interval.
We consider the sequence of iterates starting from $x$: $x$, $F(x)$, $F(F(x))$, and so on.
Given $F$ and $x$, does this sequence reach a fixed point of $F$?

Decidability is also unknown for the reachability variant: given $F$ and $x$, and $y$, does the sequence starting from $x$ reach $y$ in a finite number of iterations?

It is open even when $F$ has only two linear pieces.

Remark: for this problem to make sense, $F$ and $x$ (and $y$) must have a finite description.
We assume here that $x$ is rational, and that the slopes and breakpoints of $F$ are also rational.

A reference: [Asarin 2011](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.220.7864).


---

### Answer by username_5 on 2013-09-09. Score: 2

there seems to be a fairly natural way/angle to study this question that is utilized in at least 3 papers as follows.

let $TM(k,l)$ be the set of Turing Machine with $k$ states and $l$ symbols. for low/small $k,l$ the machines are provably decidable, for larger $k,l$ past some threshhold they are provably undecidable. however in the intermediate region, they are not consistently known to be either decidable or undecidable (and the full table is presumably unknowable based on the same undecidability phenomena of the halting problem).

the results can be displayed on a grid as in some of the following refs. also in the intermediate region it is actually known that some (unresolved) machines are capable of simulating the Collatz conjecture for some inputs.

therefore there is clearly a ["transition-point"](http://www.cse.unsw.edu.au/~tw/phase.ppt) like phenomena operating here but not within a computable region but in an unusual sense of between computable and uncomputable.

* [Small Turing machines
  and generalized busy beaver competition](http://www.dm.unito.it/~cerruti/ac/paperpm1.pdf) Michel
* [The complexity of small universal Turing
  machines: a survey](http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf) Woods, Neary
* [On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results](http://arxiv.org/abs/0906.3329) De Mol


---

### Answer by username_5 on 2013-09-05. Score: -3

[cellular automata](http://en.wikipedia.org/wiki/Cellular_automaton), very simple computing devices, have various open questions about undecidability. some of the standard Wolfram CAs are conjectured to be universal (although a simple list of those conjectured undecidable does not seem to be available). in particular CA [Rule 54](http://mathworld.wolfram.com/Rule54.html) is conjectured by Wolfram to be Turing-complete. there are only $2^8$ basic CAs which most are now resolved as not Turing complete, but at least one was relatively recently found to be Turing complete, [rule 110](http://en.wikipedia.org/wiki/Rule_110), in a remarkable proof by Cook, using the CA to emulate a Turing-complete [tag system](http://en.wikipedia.org/wiki/Tag_systems).

also as an example of a "near miss", or "open question relatively recently resolved as TM complete", the [Wolfram 2,3 machine was proved universal in 2007 for a $25K prize](http://www.wolframscience.com/prizes/tm23/index.html). the contest was announced in May 2007 and the contest [announced the winner Smith in October 2007](http://www.wolframscience.com/prizes/tm23/solved.html).


---

### Answer by username_5 on 2013-09-04. Score: -10

there is a fairly natural way to map most open problems onto questions of (un)decidability. most open problems generally are not known to be provable or unprovable.

on the web there is some informal confusion about the undecidability of the [P vs NP](http://en.wikipedia.org/wiki/P_vs_np) problem, which is not strictly a decision problem, therefore to talk about its undecidability is not technically correct. but on the other hand there does seem to be a close/natural link between undecidability and provability as follows.

for example consider

> the language $L$ of binary strings where a string/integer $x$ is in the language iff there exists a $O(n^x)$ DTime TM that solves an NP complete problem

is this language decidable? that is an question about a language with its decidability open that is basically closely tied (even, virtually identical) to the P vs NP problem and its inherent (un?)provability.

as for P vs NP as "simple to describe", it only requires concepts of [TMs](http://en.wikipedia.org/wiki/Turing_machine), [Big O runtime notation](http://en.wikipedia.org/wiki/Big_O_notation), [nondeterminism](http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine) which are a fairly simple (some of the most basic concepts of TCS) and taught at the undergraduate level or which a gifted high school student could understand.

in fact NP vs P/Poly is also open, and can be mapped onto an open question about decidability in the same way, and this can be stated as a fairly simple problem about the growth of minimal (monotone?) circuits to recognize NP complete problems (eg cliques).

> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/100805/discussion-on-answer-by-username_5-a-simple-decision-problem-whose-decidability-is-not).  

---

