# What are the most attractive Turing undecidable problems in mathematics?

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.

-
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

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.

-

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

-

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

-

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.

-

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.

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

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

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

-

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

-
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. (http://www.inma.ucl.ac.be/~blondel/publications/99BBKPT-plstab.pdf)

-

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

-

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.

-

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 (?)
-
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