116
$\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$
  • 8
    $\begingroup$ I guess Qiaochu's question dissapeared in the process of being merged? Can someone post the link regarding PDE's that was on his question? $\endgroup$ – Mariano Suárez-Álvarez Jan 12 '10 at 19:40

44 Answers 44

6
$\begingroup$

Rice's Theorem is interesting. It states that only trivial properties of programs are decidable.

http://mathworld.wolfram.com/RicesTheorem.html

$\endgroup$
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$
  • 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$ – Joel David Hamkins Jul 2 '10 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$ – Timothy Chow Jul 4 '10 at 1:37
5
$\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$

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$

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

$\endgroup$
4
$\begingroup$

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

$\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$
  • $\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$ – Andreas Blass Jul 29 '12 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$ – Nate Ackerman Jul 30 '12 at 9:22
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$
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$
  • $\begingroup$ nice, but does it answer the question $\endgroup$ – Hans Mar 5 '13 at 20:00
2
$\begingroup$

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

$\endgroup$
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$
-4
$\begingroup$

Wait, I thought there were no intermediate Turing degrees below the halting problem (which is in degree 0').

Undecidable problem from programming:

  • Whether a given grammar is context free (?)
$\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.