135
$\begingroup$

What are the most attractive Turing undecidable problems in mathematics?

There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on the Wikipedia page.

Standard community wiki rules. One example per post please. I will accept the answer I find to be the most attractive, according to the following criteria:

  • Examples must be undecidable in the sense of Turing computability. (Please not that this is not the same as the sense of logical independence; think of word problem, not Continuum Hypothesis.)

  • The best examples will arise from natural mathematical questions.

  • The best examples will be easy to describe, and understandable by most or all mathematicians.

  • (Challenge) The very best examples, if any, will in addition have intermediate Turing degree, strictly below the halting problem. That is, they will be undecidable, but not because the halting problem reduces to them.

Edit: This question is a version of a previous question by Qiaochu Yuan, inquiring which problems in mathematics are able to simulate Turing machines, with the example of the MRDP theorem on diophantine equations, as well as the simulation of Turing machines via PDEs. He has now graciously merged his question here.

$\endgroup$
2

43 Answers 43

1
2
6
$\begingroup$

For completeness: Non trivial properties of languages are undecidable.

$\endgroup$
2
  • $\begingroup$ Yes, they are undecidable from the programs that decide them. See Rice's Theorem: en.wikipedia.org/wiki/Rice's_theorem $\endgroup$ Jun 24, 2010 at 18:35
  • $\begingroup$ Yes, this is Rice's theorem. I am stating it for completeness of the list: I don't see it listed. $\endgroup$ Jun 24, 2010 at 19:08
5
$\begingroup$

Not mentioned yet, that any computer language extended with non-deterministic features is also Turing computable.

This is interesting, because it allows the language to be simplified. If the programs operate on objects that are nil or a pair. Then you only need five instructions:

  • The constant nil
  • A pair operator
  • A sequence operator, that executes one code fragment after another
  • An inverse operator
  • A closure operator, which repeats a code fragment zero or multiple times

If you want to construct a piece code of that adds the two values of a pair, then first make something that construct (a - 1, b + 1) from (a, b). Then take the closure. This will generate (a - n, b + n). Finally, pick the value (0, c) and output c. This can be done by using the inverse operator on the pair and nil.

So, programming is a little bit odd, because you select the right value outside the loop (closure), rather than inside the loop, as in deterministic languages. The advantages is the much more simpler structure. No variables, no recursion, no matching operators (just use the inverse) and no control-structures, except closure.

This makes it a little bit between programming and mathematics. The simpler structure, allows easier mathematical reasoning. So, it might be an idea to convert a program in a deterministic language, to a program of a simplified non-deterministic language, before doing any mathematics on the program.

Lucas

$\endgroup$
5
$\begingroup$

In your last criterion, you are essentially asking for a "natural" problem that is nonrecursive, recursively enumerable, and is not complete for the recursively enumerable sets. Post proved the existence of such problems in Recursively enumerable sets of positive integers and their decision problems, for many-one reductions. Friedberg and Muchnik proved this also holds for Turing reductions, in separate papers Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944) and On the unsolvability of the problem of reducibility in the theory of algorithms. Whether these are "attractive" is probably determined by whether you like nonconstructive arguments. For a clear and self-contained exposition of these results, see Kozen's book Theory of Computation.

So this is only a partial answer, and it would still be nice to exhibit a real problem with intermediate degree.

Edit: in the survey Degrees of Unsolvability (which appears to be a chapter of an unpublished Volume 9 of the Handbook of the History of Logic), Ambos-Spies and Fejer state "it is fair to say that every particular c.e. set of natural numbers that has arisen from nonlogical considerations so far is either computable or complete... Thus one could say that the great complexity in the structure of the c.e. degrees arises solely from studying unnatural problems." This is quite a negative assessment! On a more positive note, Feferman showed in Degrees of Unsolvability Associated with Classes of Formalized Theories that every c.e. degree arises as the degree of some recursively axiomatizable consistent theory of first-order predicate calculus.

$\endgroup$
3
  • 1
    $\begingroup$ Yes, to find what you call a real problem was my point. One can build intermediate degrees via priority argument constructions, and I like those argumens very much (and I do find them constructive), but to my knowledge there is no such intermediate degree arising outside such constructions. I would also recommend Soare's book on the Computably Enumerable Sets and Degrees. $\endgroup$ Jul 2, 2010 at 20:13
  • 2
    $\begingroup$ I don't know if this counts, but "exotic" c.e. sets do arise in the results of Nabutovsky and Weinberger on Riemannian geometry. See Soare's exposition "Computability theory and differential geometry." $\endgroup$ Jul 4, 2010 at 1:37
  • 1
    $\begingroup$ Thx for adding that info but a small correction. The Friedburg-Muchnick result is kinda what is meant by non-natural. A natural problem would be one which, at a minimum, is defined in some way other than via a priority argument. Credit for solving that question generally goes to Harrington (might be forgetting a coauthor but only Harrington was my grad advisor so hopefully they'll understand) who discovered a certain property expressed in terms of the structure of r.e. sets which is only satisfied by incomplete sets. $\endgroup$ Oct 16, 2021 at 13:34
4
$\begingroup$

My own favorite is that effective first-order theories are in general semi-decidable (ie, recursively enumerable), which follows from the conjunction of Godel's completeness and incompleteness theorems.

$\endgroup$
4
$\begingroup$

Type inference for sufficiently powerful type systems, e.g. System F

$\endgroup$
4
$\begingroup$

In control theory, simultaneous stabilization of 3 or more systems is undecidable (necessary and sufficient conditions for simultaneous stabilization of 2 systems are known). This and other stabilization problems are discussed in Blondel and Tsitsiklis, A survey of computational complexity results in systems and control, Automatica, 2000, vol36 n9 p1249--1274, and its references.

$\endgroup$
4
$\begingroup$

Here's a nice one: V. D. Blondel, O. Bournez, P. Koiran, C. Papadimitriou, J. N. Tsitsiklis, Deciding stability and mortality of piecewise affine dynamical systems, Theoretical Computer Science, 255: (1-2), pp. 687-696, 2001. (http://www.inma.ucl.ac.be/~blondel/publications/99BBKPT-plstab.pdf)

$\endgroup$
4
$\begingroup$

Given a finite relational language with at least one binary relation, the question of which formulas are finitely satisfiable (i.e. realized in at least one finite structure) is $\Sigma^0_1$ but not computably enumerable (by Trakhtenbrot's Theorem)

$\endgroup$
2
  • $\begingroup$ It's the other way around: Finite satisfiability is computably enumerable (by searching systematically through all finite structures) but not decidable and thus not $\Pi^0_1$. (It's the reverse of what happens for satisfiability in arbitrary (not necessarily finite) structures.) (This is word-for-word my earlier comment, now deleted, except for fixing a couple of typos, one of which was omission of "not" before "decidable".) $\endgroup$ Jul 29, 2012 at 22:45
  • $\begingroup$ Woops. I fixed it. I had initially thought to write "finitely valid" but decided to say "satisfisfiable" instead and forgot to change the $\Pi$ to $\Sigma$. Thanks. $\endgroup$ Jul 30, 2012 at 9:22
4
$\begingroup$

As a computer scientist, it would be nice to know if a program contains buffer overflows or deadlocks.

$\endgroup$
3
$\begingroup$

The emptiness problem for 1-way probabilistic finite state automata is undecidable. (See Condon Lipton Frievalds (sp?).)

$\endgroup$
3
$\begingroup$

Say that an algorithm is reliable if given a string $S$ and integer $N$, it either halts and prints $|S|>N$ (meaning that Kolmogorov complexity of the string $S$ is greater than $N$) or does not halt, and never gives a false answer. For example, an algorithm that never halts on any input is reliable.

For any reliable algorithm $A$ there exists an integer $K$ such that for all $N>K$, $A(S,N)$ does not halt on any string (but note that for all strings except a finite set, $|S|>N$ actually holds).

$\endgroup$
1
  • $\begingroup$ nice, but does it answer the question $\endgroup$
    – Hans
    Mar 5, 2013 at 20:00
2
$\begingroup$

Note that any set of intermediate Turing degree must lie in $L$; so I nominate the least such, with respect to the canonical ordering of $L$.

I suppose this set might have already been mentioned--it's hard to say.

$\endgroup$
1
$\begingroup$

As an extension of Matiyasevich's theorem, there is a constant $c$, and a Diophantine equation on $n+1$ parameters and $m$ variables:

$$D(K,a_1,a_2,\cdots,a_n,x_1,x_2,\cdots,x_m)=0$$

including a parameter $K$ such that, for each $K\ge c$, there is no algorithm to determine whether the Diophantine equation has an infinite number of solutions or a finite number of solutions.

A similar result holds by replacing "infinite" with "even" and "finite" with "odd."

Here, the Diophantine equation has an infinite (resp. even) number of solutions iff the $K$'th bit of $\Omega$ is $1$ (where $\Omega$ is Chaitin's Constant.)

See, e.g., Ord and Kieu, "On the existence of a new family of equations for $\Omega$" (link)

$\endgroup$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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