## 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 2010 at 19:40

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.

-

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

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

-

My favorite example is the halting problem for Conway's "FRACTRAN" programming language: given a finite sequence of fractions q1, q2, ...., q_n, does the procedure "starting with a given integer and keep successively multiplying by the first element in the sequence which results in the product still being an integer until none of them do" halt? In fact there is specific sequence of fractions that is quite short which can be interpreted as a Universal machine.

-

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

-

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)

-

There is no algorithm that given a positive integer $K$ can decide if the following concrete Diophantine equation has a solution over non-negative integers:

\begin{align}&(elg^2 + \alpha - bq^2)^2 + (q - b^{5^{60}})^2 + (\lambda + q^4 - 1 - \lambda b^5)^2 + \\ &(\theta + 2z - b^5)^2 + (u + t \theta - l)^2 + (y + m \theta - e)^2 + (n - q^{16})^2 + \\ &((g + eq^3 + lq^5 + (2(e - z \lambda)(1 + g)^4 + \lambda b^5 + \lambda b^5 q^4)q^4)(n^2 - n) + \\ &(q^3 - bl + l + \theta \lambda q^3 + (b^5-2)q^5)(n^2 - 1) - r)^2 + \\ &(p - 2w s^2 r^2 n^2)^2 + (p^2 k^2 - k^2 + 1 - \tau^2)^2 + \\ &(4(c - ksn^2)^2 + \eta - k^2)^2 + (r + 1 + hp - h - k)^2 + \\ &(a - (wn^2 + 1)rsn^2)^2 + (2r + 1 + \phi - c)^2 + \\ &(bw + ca - 2c + 4\alpha \gamma - 5\gamma - d)^2 + \\ &((a^2 - 1)c^2 + 1 - d^2)^2 + ((a^2 - 1)i^2c^4 + 1 - f^2)^2 + \\ &(((a + f^2(d^2 - a))^2 - 1) (2r + 1 + jc)^2 + 1 - (d + of)^2)^2 + \\ &(((z+u+y)^2+u)^2 + y-K)^2 = 0. \end{align}
-
What is a source for this? Does this equation mean or represent anything? – Bruno Jul 29 at 12:07
This Diophantine equation can encode any r.e. set. It is derived from "Undecidable diophantine equations" by James P. Jones, Bull. Amer. Math. Soc. (N.S.) Volume 3, Number 2 (1980), 859-862. ams.org/journals/bull/1980-03-02/… – Vladimir Reshetnikov Jul 29 at 14:56
It is clear that there is a Diophantine equation of power 4 with the same property (just add enough auxiliary variables and clauses of the form $(v_1 - v_2 v_3)^2$), but it is unknown if there is one of power 3. – Vladimir Reshetnikov Jul 29 at 21:24
show 1 more comment

My favourite is related to the Kolmogorov Complexity of a string:

The problem of deciding if a string $s$ is compressible ($K(s) <^? |s|$) is undecidable

-

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.

-

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.

-

A variant of the "given a finite simplicial complex, is it the 5-sphere?" problem is the "given a finite simplicial complex, is it it a 6-manifold?".

I find this attractive because, because manifolds are such a basic and fundamental concept, you'd expect we'd be able to recognize one, but in fact we cannot.

This was pointed out by an answer to the question: http://mathoverflow.net/questions/71400/when-are-finite-simplicial-complexes-smooth-manifolds

-

The following undecidable problem is natural for engineers in the sense that runtime estimation is an ubiquitous engineering problem associated to (for example) control theory and circuit design.

Viola's theorem  Given an integer $k$ and Turing machine $M$ promised to be in P, the question "Is the runtime of $M$ of ${O}(n^k)$ with respect to input length $n$ ?" is undecidable.

The proof of this problem's undecidability was given on TCS StackExchange by Emanuele Viola in answer to the question Are runtime bounds in P decidable?

Background

This question arose in parsing Luca Tevisan's answer on TCS StackExchange to the question Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes).

The illumination sought in asking/answering this question was a better appreciation/intuition regarding the practical aspects of runtime estimation in the complexity class P, in the sense of runtime estimates that are feasible (that is, require computational resources in P), versus infeasible (that is, require computational resources in EXP), versus formally undecidable (the instance above).

What this problem's undecidability shows us, perhaps, is that some aspects of P are richer and more subtle than is readily appreciated upon first acquaintance.

-

Richardson's theorem says that it is undecidable to tell whether an expression $E$ satisfies $E=0$, where $E$ is generated by $\mathbb{Q}\cup\{\pi,\ln 2,x\}$ and the composition of operations in $\{+,-,\times,\sin,\exp, \mathrm{abs}\}$.

(I thought this deserves its own answer, even if it's given as a comment on this other answer.)

-

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

-

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 2011 at 10:43

Above it was mentioned that, from a general finite group presentation, it is not decidable whether the group is finite. There are acutally a bunch of group properties that are similarly undecidable - is it abelian, solvable, simple? But my favourite would be : does it have more than one element!?

-

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.

-
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 2010 at 20:13
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 2010 at 1:37

Suppose we specify a group $G$ by a set of relations, e.g. $x_1x_2x_3^{-1} = 1$. Then, the problem of determining if $G$ is finite or not is undecidable.

-
Thanks for this example. To supplement your description, the undecidable problem is: given a finite group presentation, determine if the group it presents is finite or infinite. – Joel David Hamkins Jul 2 2010 at 20:20

Team games, as defined in Bob Hearn's thesis or the book Games, Puzzles, and Computation. These are games, like bridge, in which there are two teams playing against each other and each team has several players who do not have complete information about the game. The astounding thing is that even though there are only finitely many game states, it is undecidable to determine whether there is a winning strategy. This seeming paradox arises because the players do not necessarily know that the game state has returned to a previous state, and a winning strategy can in principle depend on the entire history of the game. I like this one because it takes some effort even to understand why it it not trivially decidable.

-
See also my note of June 3rd on this same problem. It deserves double mention! – Joseph O'Rourke Feb 18 2011 at 2:00
show 1 more comment

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

-

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

-

For completeness: Non trivial properties of languages are undecidable.

-

This I think is interesting: On a finite game board, but with an unbounded number of moves, games pitting teams against one another, in the presence of imperfect information, are undecidable. "Imperfect information" is like that in Bridge (although Bridge has a bounded number of moves). This result is proved in Games, Puzzles, & Computation by Robert Hearn and Erik Demaine, 2009.

-

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

-

The rule 110 is also a cute one.

-

A MODULAR SYSTEM $M$ is a finite set of "rules" of the form $ax+b\to cx+d$, with $a,b,c,d\in\mathbb{Z}$. If $u,v\in\mathbb{Z}$, then $u$ is "derivable" from $v$ in $M$ if one can get from $u$ to $v$ by applying rules in $M$. For example, the well-known Collatz problem asks whether for all positive integers $u$, 1 is derivable from $u$ in the modular system with the two rules $2x\to x, 2x+1\to 6x+4$.

The general problem of whether $u$ is derivable from $v$ in a given modular system $M$ is undecidable. (Proved in Borger, "Computability, Complexity and Logic").

-

I'm surprised nobody's mentioned the Post correspondence problem. Like the tiling problem, it seems like something so basic, there has to be some simple way to brute-force it... but no.

-
I second this problem, which is the gateway to many other unsolvability proofs, such as the one for the mortality problem for $3\times 3$ matrices. – John Stillwell Jun 3 2010 at 23:01

Is a given computable function $f:\mathbb{R}\to\mathbb{R}$ differentiable?

OK, I'll have to (1) clarify what I mean and (2) show it's not a completely trivial consequence of the halting problem.

Part (1):

I have to define computability of $f$. Say that a Turing machine computes a real $x$ if, given any input $n$, it always returns a sequence of $n$ rational numbers, with the $i$th element within $2^{-i}$ of $x$. In other words, it computes the initial part of a Cauchy sequence approximating $x$ to a predetermined accuracy.

Now we can say that a machine $X$ computes $f:\mathbb{R}\to\mathbb{R}$ if for any $x$, you can give it a description of a Turing machine to compute $x$ as an input, and always gives you back another one that computes $f(x)$.

It is impossible to make a machine that takes a description of a machine $X$ to compute $f$, and tells you if the function $f$ is differentiable, i.e. differentiability is undecidable.

But, you say, that's trivial. After all, the machine $X$ we're passing in as argument is, obviously, a machine, so we expect to meet the halting problem. So contrast with:

Part (2): Integration over an interval is computable.

(I've probably made some typos in the above as it's not my field. So try Computable Analysis for more details.)

-
Is there a direct analogy? And is the inverse image easy to compute in some formal sense? I also assume you're refering to $Rf_*$, not $f_*$. – Daniel Litt Jun 24 2010 at 19:22

The mortality problem for $3\times 3$ matrices: given a finite set $F$ of $3\times 3$ integer matrices, decide whether the zero matrix is a product of members of $F$ (with repetitions allowed). This was proved unsolvable by Michael Paterson, Studies in Applied Mathematics 49 (1970), 105--107.

The corresponding problem for $2\times 2$ matrices is apparently still open.

-
... or just two $21 \times 21$ matrices – Vladimir Reshetnikov Nov 29 2011 at 5:57
Interesting ... I hadn't heard that result. Do you have a reference? – John Stillwell Nov 29 2011 at 17:40

Two open problems in this area that I like:

1. (related to the Tiling Problem mentioned by Hamkins) Is it undecidable whether a polyomino (as defined e.g. at http://en.wikipedia.org/wiki/Polyomino) tiles a rectangle? If $P$ is a polyomino that tiles a rectangle, let $f(P)$ be the least number of copies of $P$ that are needed to tile a rectangle, and let $p(n)$ be the maximum of $f(P)$ over all polynominoes with $n$ squares that tile a rectangle. If the answer to the question is positive (which is what people in the area believe and is sometimes erroneously claimed to be known), then $p(n)$ grows faster than any recursive function!

2. Let $F(x)=P(x)/Q(x)$ such that $P(x)$ and $Q(x)$ are polynomials with integer coefficients and $Q(0)\neq 0$. Is it undecidable that the Taylor series expansion of $F(x)$ at $x=0$ has a zero coefficient?

-

Well if we're going to give easy ones, then: checking if two real numbers are equal. As if you needed more reasons to be disturbed by the reals!

A special case of: checking if a vector $v$ in a finite dimensional vector space over the reals is linearly independent of a set of vectors $\{u_i\}$.

(almost equivalently: checking equality (in the sense of extensionality) of $k\geq 2$ bounded integer-valued functions. the output of such functions can be written as real numbers in $[0,1]$, but you have to have to pad each integer so that you don't accidentally call two different outputs the same real number (due to $0.99\ldots = 1.00$ etc). How to solve the halting problem: have a function $f(n) = 1$. Given some arbitrary program/function, nest it in a function $g(n)$ which runs it for $n$ cycles, and outputs $1$ if it halted, $0$ otherwise. $f$ and $g$ are equivalent iff the program does not halt.)

-
Although there is a sense in which this problem is not decidable, I think it is not a "problem" in the sense of the question, in the sense of Turing computability, since it is not finitely encodable. Namely, a decidable problem is a set of natural numbers whose characteristic function is computable by a Turing machine. An undecidable problem is a set of natural numbers not computable in this way. Many mathematical objects, such as finitely presented groups, finite graphs, etc. can be finitely described, allowing Turing machines to accept such a description as input. – Joel David Hamkins Jan 13 2010 at 14:34
@Joel This still applies for computable reals. Computable reals are finitely encodable. – Dan Piponi Feb 19 2010 at 0:11