MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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

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.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|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|cite|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|cite|improve this answer
To clarify, Friedberg and Muchnik's introduction of the "finite injury method" solved Post's Problem of the existence of intermediate computably enumerable degrees. The existence of (non-computably enumerable) intermediate degrees was known before Friedberg and Muchnik via the "finite extension method" of Kleene and Post. – Asher M. Kach Mar 28 '12 at 18:29
Yes, thank you. This was precisely the point of my challenge, to find out if there are any natural examples of such intermediate degrees, particularly c.e. such degrees. All known such degrees are the result of these kind of complicated constructions aimed specifically at producing such intermediate degrees. But it could be that there are natural sets of natural numbers that happen to have intermediate degree. (For example, how about the set of differences of primes $p-q$?) It is, I believe, a major open question to find such natural instances of intermediate Turing degrees. – Joel David Hamkins Mar 28 '12 at 20:59

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|cite|improve this answer
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".) – Andreas Blass Jul 29 '12 at 22:45
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. – Nate Ackerman Jul 30 '12 at 9:22

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

share|cite|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|cite|improve this answer
nice, but does it answer the question – Hans Mar 5 '13 at 20:00

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

share|cite|improve this answer

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

share|cite|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|cite|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|cite|improve this answer
See… 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


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.