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 problem whose decidability is open?

  • 26
    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 '13 at 3:25
  • 2
    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 '13 at 12:04
  • 8
    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 '13 at 13:56
  • 6
    @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 '13 at 18:49
  • 2
    @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 '13 at 20:58

15 Answers 15

up vote 87 down vote accepted

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

  • 6
    Oh this is a good one, thanks! – Lev Reyzin Sep 5 '13 at 1:16
  • 6
    epubs.siam.org/doi/abs/10.1137/1.9781611974782.12 Igor Potapov and Pavel Semukhin recently showed this is decidable. – Chao Xu Jan 18 '17 at 19:07
  • 4
    @ChaoXu : ​ That paper seems to be only for non-singular matrices. ​ ​ ​ ​ – user6973 Sep 6 '17 at 22:24
  • 2
    @RickyDemer You are correct, my mistake. – Chao Xu Sep 7 '17 at 6:04

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

  • 7
    @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 '13 at 1:53
  • 3
    @vzn: There are ways to make the Java compiler behave badly too but I don't know the details. – Eric Lippert Oct 5 '13 at 1:53
  • 2
    @vzn Scala's language of types is Turing complete, and hence Scala's type-checker can loop. See here for details. The same is true for Haskell. I am insufficiently familiar with C# and Java to know if one can get their repective type-checkers to loop. – Martin Berger Oct 7 '13 at 20:01
  • 3
    @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 '13 at 21:25
  • 7
    @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 '13 at 21:34

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

  • 1
    Thanks - do you have a link to someplace that says it's open? – Lev Reyzin Sep 4 '13 at 17:42
  • 1
    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 '13 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 '13 at 5:24
  • 2
    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 '13 at 11:45
  • 1
    @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 Sep 26 '13 at 21:31

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


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

enter image description here

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

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

  • 12
    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 '13 at 1:20
  • @LevReyzin Thanks. Edited to fix the issue. – Mohammad Al-Turkistany Sep 7 '13 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 '13 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 '13 at 14:29

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.

It is unknown whether or not it is decidable to determine if a given shape can tile the plane.

            

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.

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?

(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

Iterated maps on the interval (description from here):

(very related to the problem proposed by Magnus Find)

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.

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 '13 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.

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

  • 3
    $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 '13 at 22:24
  • this assumes either P=NP or P$\ne$NP which is not nec the case if its unprovable. – vzn Sep 4 '13 at 23:25
  • 1
    saying that an integer is uncomputable is nonsense. and i don't think the principle of the excluded middle is affected by whether the statement is provable. – Sasho Nikolov Sep 5 '13 at 22:19
  • 5
    either fix your answer or stop leaving comments. I have seen these questions, but if you are unable to use them or the answers given to them to fix your own complete mess of an answer, or, worse, if you do not want to, maybe you should go troll another community. – Sasho Nikolov Sep 19 '13 at 21:21
  • 5
    to the point, the problem in your answer is trivially decidable, regardless of the resolution or formal independence of the P vs NP problem from ZFC. also, creating problems that are possibly undecidable or trivially decidable depending on the truth of a famous conjecture is nothing more than a cute exercise (that you are so far completely failing at), and in most cases shows nothing about the intrinsic difficulty of a conjecture. – Sasho Nikolov Sep 19 '13 at 21:27

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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