Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
5  
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? –  Mariano Suárez-Alvarez Jan 12 '10 at 19:40

42 Answers 42

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.

share|improve this answer
1  
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. –  Joel David Hamkins Jul 2 '10 at 20:13
2  
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." –  Timothy Chow Jul 4 '10 at 1:37

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

For your "challenge" question, note that it is extremely hard to construct examples of problems of degree strictly less than the halting problem. In fact this was a question open for some years under the name of Post's problem. It was finally solved by the invention of the "finite injury method" which gave many examples of such problems. However I do not know of any naturally formulated problem with degree strictly less than the halting problem.

share|improve this answer

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

share|improve this answer

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)

share|improve this answer

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

share|improve this answer

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

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

share|improve this answer

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)

share|improve this answer

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.

share|improve this answer

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 (?)
share|improve this answer
4  
See en.wikipedia.org/wiki/… for a discussion of the fact that there are intermediate degrees between $a$ and $a'$ for every degree $a$. –  Joel David Hamkins Feb 18 '11 at 10:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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