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
4  
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
add comment

41 Answers

The Word Problem for groups is undecidable. This is the problem, given a finite group presentation and a word, to decide if that word is the group identity in that presentation. The problem is undecidable because one may encode the Halting problem for Turing machines. Basically, for each Turing machine program, one can construct a group presentation and a word, such that the program halts if and only if that word is the identity.

share|improve this answer
3  
Closely related is that computing $H^2$ of a finitely-presented group is impossible: Gordon, C. Some embedding theorems and undecidability questions for groups. Combinatorial and geometric group theory (Edinburgh, 1993), 105--110, London Math. Soc. Lecture Note Ser., 204, Cambridge Univ. Press, Cambridge, 1995. –  Ryan Budney Jan 12 '10 at 18:03
1  
There are numerous closely related problems. The conjugacy problem, for example, is the problem of deciding whether two words are conjugate in a given presentation. Also: deciding the order of a group element or deciding whether the order exceeds a given number. –  Joel David Hamkins Jan 13 '10 at 14:21
2  
Joel, I take your point. I was thinking that a solvable word problem would remain solvable when a relation $x=1$ is added, but on second thoughts this is not clear. Nonetheless, I'm still dubious about Victor's proposed reduction. If $y=1$ in "$G$ plus $x=1$" it could be, e.g., that $y=zx^{2}z^{-1}$ in $G$, so $y$ is conjugate to $x^2$ but not necessarily to $x$. –  John Stillwell May 26 '10 at 3:05
show 10 more comments

The Tiling problem is undecidable. This is the problem, given a finite set of tile types, to determine whether there is an arrangement of them with adjacent sides matching that tiles the plane. The problme is undecidable because the Halting problem for Turing machines reduces to it, in the sense that every Turing machine program corresponds to a tiling problem, which has a tiling if and only if the program fails to halt. Basically, the run of the machine is encoded into the tiling, which can continue as long as the program keeps running.

share|improve this answer
2  
Moreover, the tiling extension problem is undecidable: can a tiling of a part of the plane be extended to the whole plane? There are some interesting examples of partial Penrose tilings with many pieces which are non-extendable in a non-obvious way. –  Victor Protsak May 25 '10 at 4:11
3  
This has a consequence of interest to 3-manifold topologists, concerning branched surfaces --- a branched surface is a compact 2-complex such that at each point $x$ there is a well-defined "tangent plane", and there exists a smoothly embedded open disc containing $x$. Ramin Naimi (unpublished) proved that if a branched surface is embeddable in a 3-manifold then it is decidable whether every 2-cell is in the image of a complete immersion of $R^2$. However, for abstract branched surfaces, this is undecidable, because every tiling problem can be encoded as an abstract branched surface. –  Lee Mosher Mar 28 '12 at 16:35
show 1 more comment

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|improve this answer
add comment

The recognition problem for compact, simply connected contact manifolds of given dimension $2n-1\geq 11$ (Seidel, 2007).

A contact structure on a $(2n-1)$-manifold is a tangent hyperplane field $\xi$ which can locally be written as $\ker\alpha$ for a 1-form $\alpha$ with $\alpha \wedge (d\alpha)^{n-1}$ non-vanishing. In principle there are finite ways to specify contact manifolds, using symplectic handlebody theory. But there's a simply connected contact manifold $(M_0,\xi_0)$ with the property that, given another, say $(M,\xi)$, the problem of deciding whether it's isomorphic to $(M_0,\xi_0)$ contains an algorithmically-unsolvable word problem for groups.

If you forget the contact structure, algorithmic recognition is possible (Nabutovsky-Weinberger).

share|improve this answer
add comment

The problem of distinguishing two manifolds (up to homeomorphism, or even homotopy equivalence Edit: given a triangulation) is undecidable. This follows from the word problem applied to fundamental groups.

There are similar problems concerning simplicial complexes, e.g., whether a given complex is a triangulation of a manifold.

share|improve this answer
2  
Distinguishing two manifolds given what information? How do you "give" somebody two manifolds, and ask them if they are homotopy equivalent? Do you mean if I give you an atlas for each manifold? Because I would still say this is a problem with distinguishing between representations. –  Steven Gubkin Jan 12 '10 at 18:53
1  
There are many ways of making a precise statement. You could give a simplicial complex underlying a manifold. Or a handlebody decomposition (e.g. a Kirby diagram for a 4-manifold). Or even a finite list of polynomial equations with integer coefficients (whether this accounts for all manifolds doesn't really matter). –  Tim Perutz Jan 12 '10 at 19:16
4  
An interesting special case is the problem of recognizing the $n$-sphere, proved unsolvable for $n\ge 5$ by S.P. Novikov in 1962. Incidentally, S.P. Novikov is the son of P.S. Novikov, who proved the unsolvability of the word problem for groups. –  John Stillwell May 24 '10 at 22:34
show 3 more comments

From what I've been told, it is impossible to decide whether (in general) a complex holomorphic function has a zero at the origin. Similarly, it is undecidable whether certain holomorphic functions have double zeros or zeros just "really" close to each other. [It would really be interesting if this had some effect on things like the Riemann hypothesis or BSD.]

share|improve this answer
1  
Statements like this do have an effect on the decidability of the Risch algorithm (en.wikipedia.org/wiki/Risch_algorithm). –  Qiaochu Yuan Jan 12 '10 at 17:29
2  
What data is given on the function? –  Mariano Suárez-Alvarez Jan 12 '10 at 19:36
2  
Re: Ryan -- As one can express real numbers such that there is no algorithm to determine if they are equal to zero, the answer is still no. [So, in some ways that makes my answer trivial, since then polynomials work. But see the other comment below.] Re: Mariano -- That's the big question! How much information can we give and still be unable to determine whether such a function has a zero? For a concrete example: Given the L-function associated to a rational elliptic curve of rank 4, can we algorithmically prove the analytic rank is 4? From what I understand this is still open! –  Pace Nielsen Jan 19 '10 at 16:11
1  
In Risch algorithm here is heuristic procedure needed in order to check if some algebraic form is equal to zero. This is because of The Theorem of Richardson which states what algebraic formulas are undecidable, see here mathworld.wolfram.com/RichardsonsTheorem.html. –  kakaz Feb 16 '10 at 12:19
show 1 more comment

As I mentioned in the other thread, Matiyasevich's theorem implies that it is undecidable whether a system of Diophantine equations over $\mathbb{Z}$ has a solution (Hilbert's 10th Problem). I have to mention some related results here: if $\mathbb{Z}$ is replaced by $\mathbb{F}_p[t]$ then the problem is still not decidable, if replaced by $\mathbb{R}, \mathbb{C}, \mathbb{Q}_p$ then the problem is decidable, and if replaced by $\mathbb{Q}$ or $\mathbb{F}_p((t))$ the answer is not known! (Reference.) I believe it is not even known whether the answer is yes for some number fields but no for others (which would be truly bizarre).

share|improve this answer
1  
Thanks very much, Qiaochu, for moving your question over here. I appreciate it, and I think we'll get a good list. –  Joel David Hamkins Jan 12 '10 at 17:27
7  
I find these results really interesting; in a way it shows why analysis is so successful. –  Sam Derbyshire Jan 12 '10 at 20:13
add comment

Let $n\geq 3$. Given two embeddings of $S^n$ into $\mathbb{R}^{n+2}$, the problem of determining whether they are equivalent (via a deformation of $\mathbb{R}^{n+2}$) is undecidable (the case $n=2$ is open; for $n=1$ an algorithm exists).

By the way, Bjorn Poonen has a wonderful talk on this topic, titled Undecidability Everywhere.

share|improve this answer
9  
It's still undecidable up to an ambient homeomorphism. And the undecidablility is again a fundamental group issue -- there's a certain type of group presentation called a Wirthinger presentation. Given any such presentation there's an algorithm to construct a knot ($n>2$) such that $\pi_1$ of the complement has that Wirthinger presentation. –  Ryan Budney Jan 12 '10 at 20:57
show 2 more comments

Four from Compiler Science:

  1. Does a program ever access an uninitialized variable.
  2. Do two context free grammars describe the same langauge.
  3. Does it make a difference if parameters to a subroutine are passed by reference or by copy-result
  4. Deadlock determination in parallel programs.

Actually almost every question of the form "Does a program ever do X?" is equivalent to the halting probelm. So the above might be considered too close the the halting problem to be interesting answers ot this question.

share|improve this answer
1  
Aren't these just special cases of Rice's Theorem? –  Christoph-Simon Senjak Mar 7 '13 at 21:41
show 2 more comments

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

share|improve this answer
add comment

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

share|improve this answer
3  
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 '10 at 14:34
13  
@Joel This still applies for computable reals. Computable reals are finitely encodable. –  Dan Piponi Feb 19 '10 at 0:11
show 4 more comments

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?

share|improve this answer
show 1 more comment

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.

share|improve this answer
8  
... or just two $21 \times 21$ matrices –  Vladimir Reshetnikov Nov 29 '11 at 5:57
4  
Interesting ... I hadn't heard that result. Do you have a reference? –  John Stillwell Nov 29 '11 at 17:40
3  
Halava, V.; Harju, T.; Hirvensalo, M. (2007). "Undecidability Bounds for Integer Matrices Using Claus Instances". International Journal of Foundations of Computer Science 18 (5): 931–948. citeseerx.ist.psu.edu/viewdoc/… –  Vladimir Reshetnikov Jul 30 '12 at 0:00
1  
Note the recent preprint arxiv.org/abs/1312.6700 which improves these results. Undecidability now holds for five 3*3 matrices or two 15*15 matrices. –  subshift Feb 17 at 14:36
show 1 more comment

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

share|improve this answer
1  
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 '10 at 19:22
show 5 more comments

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.

share|improve this answer
1  
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 '10 at 23:01
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

For completeness: Non trivial properties of languages are undecidable.

share|improve this answer
show 3 more comments

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

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

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.

share|improve this answer
1  
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 '10 at 20:20
add comment

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
add comment

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!?

share|improve this answer
add comment

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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.