# A simple problem whose decidability is not known

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering on discussing the concept of decidability. I want to give an example of a problem which 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 problem whose decidability is open?

-
Collatz Problem is simple-to-describe problem whose decidability is open. A generalization of the Collatz problem was shown to be undecidable. math.mit.edu/~poonen/papers/sampler.pdf mathworld.wolfram.com/CollatzProblem.html –  Mohammad Al-Turkistany Sep 4 at 3:25
Perhaps you can also show this nice "trick": write a small program (you can call it "goldbach") that iterates through the even integers $n_i \geq 5$ and checks that $n_i = p_j + p_k$ for some primes $p_j, p_k<n_i$ and stops in the negative case ... then say "well, we don't' know if the halting problem for this program is decidable!" :-). It shows the strong correlation between number theory problems and the halting problem. –  Marzio De Biasi Sep 4 at 12:04
These seem nice, but the concept of decidability doesn't apply for just one specific instance, since for both these cases, the answer is just a fixed yes/no. –  Lev Reyzin Sep 4 at 13:56
@MarzioDeBiasi, that's not a "strong correlation" between the halting problem and number theory. Any conjecture of the form "frangible widgets do/do not exist" can be turned into a program that halts iff there's a frangible widget, as long as frangibility is decidable and widgets are recursively enumerable. The existence of such a program is only the most trivial link between the halting problem and widget theory. –  David Richerby Sep 4 at 18:49
@DavidRicherby: fairly convincing :-) . I was only trying to bring out the fact (surprising for me) that resolving the halting problem for a few bits of code corresponds to solve a long standing mathemathical conjecture. So I should replace "strong correlation" with "weak correlation but astonishing for me" :-) :-) –  Marzio De Biasi Sep 4 at 20:58

The Matrix Mortality Problem 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.)

-
Oh this is a good one, thanks! –  Lev Reyzin Sep 5 at 1:16

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

-
@vzn: The Microsoft C# compiler can be made to go into an unbounded recursion. See my article on the subject: blogs.msdn.com/b/ericlippert/archive/2008/05/07/… –  Eric Lippert Oct 5 at 1:53
@vzn: There are ways to make the Java compiler behave badly too but I don't know the details. –  Eric Lippert Oct 5 at 1:53
@vzn: Also this might be of interest to you: overload resolution in C# 3 is at least NP-HARD because you can force the compiler to solve arbitrary SAT problems: blogs.msdn.com/b/ericlippert/archive/2007/03/28/… –  Eric Lippert Oct 7 at 21:25
@vzn: I should add: though the C# compiler can be made to go into such a recursion, that is because we did not implement Andrew Kennedy's algorithm for detecting and rejecting the type topologies that lead to this particular unbounded recursion. Had we done so then this one could be eliminated but then we wouldn't have a C# compiler anymore because some previously legal C# programs would become illegal. –  Eric Lippert Oct 7 at 21:30
@vzn: Finally, the question "is this somewhat academic?" is of course answered yes. The question "is blah known to be decidable?" is by its nature an academic question. These cases do not arise in realistic line-of-business code. The importance of this question from an engineering perspective is in security; can a hostile third party provide code where analyzing it before running it can itself cause bad behavior? That is the situation we're in on the internet, where hostile third parties send JavaScript to your browser. –  Eric Lippert Oct 7 at 21:34

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

-
Thanks - do you have a link to someplace that says it's open? –  Lev Reyzin Sep 4 at 17:42
See www-math.mit.edu/~poonen/papers/subrings.pdf (second paragraph). There is also an expository article at www-math.mit.edu/~poonen/papers/aws2003.pdf –  Boris Bukh Sep 4 at 21:20
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 Sep 6 at 5:24
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 Sep 6 at 11:45
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 Sep 19 at 17:22

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

-

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

Infinite chess:

Input: A nite 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.

Another simple problem is the behaviour of Langton's 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"?

For infinite support the problem is undecidable, see: A. Gajardo, A. Moreira1 and E. Goles, Complexity of Langton’s ant

-

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

-
Here's a related article. –  Martin Berger Sep 5 at 14:11
@Martin Berger: The ToDS version is better, since it includes the NP-hardness proof above, has full proofs, and is open access. Prepublication link: tods.acm.org/accepted/2013/SalamonClassification.pdf –  András Salamon Sep 5 at 16:02

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, BJORN POONEN

2- Weisstein, Eric W. "Collatz Problem." From MathWorld--A Wolfram Web Resource.

3- The 3X+1 Problem: An Overview, Jeffrey C. Lagarias

-
Strictly speaking, the answer to your particular question is simply either "yes" or "no," so it cannot be undecidable. On the other hand, telling whether a particular number is a Collatz number might be undecidable. –  Lev Reyzin Sep 7 at 1:20
@LevReyzin Thanks. Edited to fix the issue. –  Mohammad Al-Turkistany Sep 7 at 5:55
glad this answer is now included & suggest all other major open number theory problems can be formulated similarly as in other comments/answer & think this fundamental link is close to a pivotal bridge theorem unexplored by theoretical communities. –  vzn Sep 7 at 14:31
study of Collatz conjecture from a more TCS/empirical angle with many refs here (eg via FSM transducer recursion, tag system etc) –  vzn Sep 14 at 14:29

Post's Correspondence problem 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.

-

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.

-

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" like phenomena operating here but not within a computable region but in an unusual sense of between computable and uncomputable.

-
ps the De Mol ref pdf was not downloadable for me from arxiv at the time of writing, it hangs –  vzn Sep 9 at 18:42
cellular automata, 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 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, in a remarkable proof by Cook, using the CA to emulate a Turing-complete tag system.
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. the contest was announced in May 2007 and the contest announced the winner Smith in October 2007. - add comment 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 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, Big O runtime notation, nondeterminism 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). -$L$is decidable: either no such algorithm exists for any$x$and$L = \emptyset$, or P = NP, which means that all languages in P are NP-complete; for all$x$there exists a language in P that requires time$\Theta(n^x)$to solve, so even if you define$L$with respect to optimal running times, it still would be equal to all integers. So$L$is either empty or all integers, and decidable in either case. – Sasho Nikolov Sep 4 at 22:24 this assumes either P=NP or P$\ne$NP which is not nec the case if its unprovable. – vzn Sep 4 at 23:25 also it cannot be ruled out from current knowledge that P=NP and the$x$in the$O(n^x)\$ is uncomputable... this is not merely/entirely academic, eg in the Gasarch 2012 P vs NP poll, 3% of researchers responding believe it to be independent/unprovable –  vzn Sep 5 at 15:04