135
$\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.

Improve this question
$\endgroup$
2

43 Answers 43

Reset to default
1
2
6
$\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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Jul 2, 2010 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
    Commented Jul 4, 2010 at 1:37
  • 1
    $\begingroup$ Thx for adding that info but a small correction. The Friedburg-Muchnick result is kinda what is meant by non-natural. A natural problem would be one which, at a minimum, is defined in some way other than via a priority argument. Credit for solving that question generally goes to Harrington (might be forgetting a coauthor but only Harrington was my grad advisor so hopefully they'll understand) who discovered a certain property expressed in terms of the structure of r.e. sets which is only satisfied by incomplete sets. $\endgroup$
    – Peter Gerdes
    Commented Oct 16, 2021 at 13:34
  • $\begingroup$ Hi András, i can find a later paper with Ehrenfeucht where it is shown that every re set is representable in some axiomatizable theory, but i cannot download the paper you link to. What do you call "the degree of a theory" exactly ? Is it the degree of Gödel numbers of the theory - as a set of sentences ? If i understand well the problem is to keep the theory of low Turing degree when starting with a low set of axioms. $\endgroup$
    – plm
    Commented Oct 2 at 18:14
5
$\begingroup$

Let a finite structure be a finite underlying set A along with a finite set of finitary operation from A to itself. Such creatures are called algebras in the study of universal algebra, and one subarea of study is the equational theory of such a creature, i.e. the set of universally quantified equations which hold in the strucure (e.g. the associative law for semigroups).
The equational theory is said to be finitely based if there is a finite set of equations from which one can deduce precisely those equations in the equational theory.

A problem raised by Tarski and shown undecidable by McKenzie is Tarski's Finite Basis Problem: Given a finite structure , determine whether its equational theory is finitely based.

Gerhard "Ask Me About System Design" Paseman, 2010.01.12

Improve this answer
$\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

Improve this answer
$\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.

Improve this answer
$\endgroup$
4
$\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.

Improve this answer
$\endgroup$
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)

Improve this answer
$\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)

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jul 29, 2012 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
    Commented Jul 30, 2012 at 9:22
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ nice, but does it answer the question $\endgroup$
    – Hans
    Commented Mar 5, 2013 at 20:00
3
$\begingroup$

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

Improve this answer
$\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.

Improve this answer
$\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)

Improve this answer
$\endgroup$
1
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .