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.

$\endgroup$
2

43 Answers 43

135
$\begingroup$

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, doi: 10.1002/sapm1970491105.

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

Edit (11 September 2016): The problem for $2\times 2$ matrices is apparently still open, despite the solution of a seemingly similar problem mentioned in Igor Potapov's answer below.

$\endgroup$
9
  • 25
    $\begingroup$ ... or just two $21 \times 21$ matrices $\endgroup$ Nov 29, 2011 at 5:57
  • 6
    $\begingroup$ Interesting ... I hadn't heard that result. Do you have a reference? $\endgroup$ Nov 29, 2011 at 17:40
  • 8
    $\begingroup$ 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/… $\endgroup$ Jul 30, 2012 at 0:00
  • 22
    $\begingroup$ 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. $\endgroup$
    – subshift
    Feb 17, 2014 at 14:36
  • 4
    $\begingroup$ Unless the paper proves something more general than is stated in the abstract (which I don't think it does, by skimming through the paper), then the result doesn't establish general membership problem, but rather the membership problem for nonsingular matrices. Mortality problem is trivial if we restrict to sets of matrices generated by nonsingular matrices, since we can't express zero matrix as a product of nonsingular matrices. $\endgroup$
    – Wojowu
    Sep 11, 2016 at 18:14
70
$\begingroup$

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},$ or $\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).

$\endgroup$
8
  • 2
    $\begingroup$ Thanks very much, Qiaochu, for moving your question over here. I appreciate it, and I think we'll get a good list. $\endgroup$ Jan 12, 2010 at 17:27
  • 11
    $\begingroup$ I find these results really interesting; in a way it shows why analysis is so successful. $\endgroup$ Jan 12, 2010 at 20:13
  • 3
    $\begingroup$ @CiroSantilli郝海东冠状病六四事件法轮功 It would be more courteous to ask what ${\mathbb Q}_p$ is before editing Qiaochu's answer. MathOverflow is intended for professional mathematicians and people write their answers with that audience is mind; and we do not quite follow the usual StackExchange norms when it comes to rewriting other people's content $\endgroup$
    – Yemon Choi
    Dec 26, 2020 at 16:12
  • 2
    $\begingroup$ @CiroSantilli郝海东冠状病六四事件法轮功 "This question is very basic however, and possibly should not have been asked here on this site" I strongly disagree. I think this question is fine for MO. Separately, I've edited the answer - I hesitate to undo your edit unilaterally, but I think it's more gracefully done by not adding a parenthetical. $\endgroup$ Dec 26, 2020 at 20:08
  • 2
    $\begingroup$ @CiroSantilli郝海东冠状病六四事件法轮功 See here and here respectively. $\endgroup$ Dec 26, 2020 at 20:39
69
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 3, 2010 at 23:01
  • 4
    $\begingroup$ Note that arxiv.org/abs/1312.6700 (mentioned in comments to another answer) also proves PCP undecidable even when restricted to only four pairs of binary words. $\endgroup$
    – r.e.s.
    Jul 29, 2015 at 15:13
53
$\begingroup$

There is no algorithm that given positive integers $K$ and $x$ can decide if the following concrete Diophantine equation has a solution over positive integers: \begin{align} &(elg^2 + \alpha - (b-xy)q^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 + xb^5 + 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 + \\ &(((zuy)^2+u)^2 + y-K)^2 = 0. \end{align}

$\endgroup$
10
  • 14
    $\begingroup$ This sort of thing always shocks me. $\endgroup$ Jul 29, 2012 at 1:13
  • 8
    $\begingroup$ What is a source for this? Does this equation mean or represent anything? $\endgroup$
    – Bruno
    Jul 29, 2012 at 12:07
  • 13
    $\begingroup$ 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/S0273-0979-1980-14832-6/… $\endgroup$ Jul 29, 2012 at 14:56
  • 5
    $\begingroup$ 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. $\endgroup$ Jul 29, 2012 at 21:24
  • 19
    $\begingroup$ The equation is quite simple, except for that $5^{60}$ exponent... $\endgroup$ Oct 16, 2017 at 2:56
51
$\begingroup$

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.

$\endgroup$
13
  • 6
    $\begingroup$ 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. $\endgroup$ Jan 12, 2010 at 18:03
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 13, 2010 at 14:21
  • 1
    $\begingroup$ The "reduction" of the conjugacy problem to the word problem is not always computable, since there are groups with unsolvable conjugacy problem but solvable word problem. See C.F. Miller, III, On group-theoretic decision problems and their classification, Annals of Math. Studies 68 (1971). $\endgroup$ May 25, 2010 at 4:51
  • 1
    $\begingroup$ John, Victor's argument is computably reducing the conjugacy problem for one presentation to the word problem of another presentation. $\endgroup$ May 25, 2010 at 12:08
  • 4
    $\begingroup$ 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$. $\endgroup$ May 26, 2010 at 3:05
47
$\begingroup$

The Halting Problem, the mother of them all.

$\endgroup$
4
  • 10
    $\begingroup$ Is there an undecidable problem that is actually weaker than the halting problem? Most of the problems stated here can be solved using a halting problem oracle, but also the halting problem can be solved using an oracle for them. Is there an undecidable problem X that can be solved using a halting problem oracle, but the halting problem cannot be solved with an X-oracle? $\endgroup$ Aug 26, 2014 at 9:49
  • 9
    $\begingroup$ @Christoph-SimonSenjak Yes, there are such intermediate problems, strictly between the decidable sets and the halting problem. There is a c.e. problem that is not decidable, but which is not Turing-equivalent to the halting problem. This is the solution of Post's problem, solved by Friedburg-Muchnik. See en.wikipedia.org/wiki/…. $\endgroup$ Aug 26, 2014 at 9:53
  • 1
    $\begingroup$ @Christoph-SimonSenjak scottaaronson.com/democritus/lec4.html $\endgroup$
    – Andrew
    Mar 8, 2016 at 23:16
  • $\begingroup$ @Christoph-SimonSenjak cs.stackexchange.com/questions/26340/… $\endgroup$ Dec 26, 2020 at 14:40
46
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ Is the problem known to become decidable if $\operatorname{abs}$ is removed from the allowed operations? $\endgroup$ Nov 21, 2015 at 15:38
  • 3
    $\begingroup$ @DavidZhang yes, combining some later results (see dx.doi.org/10.1145/321574.321591 and dx.doi.org/10.1145/321850.321856), we can remove the dependence on $\ln 2$, $\mathrm{abs}$ and $\exp$. $\endgroup$
    – didest
    Nov 26, 2015 at 15:34
  • 1
    $\begingroup$ Is this true?! It sounds wrong. $\endgroup$
    – Vincent
    Mar 7, 2018 at 13:00
  • 2
    $\begingroup$ @didest Could you elaborate on your comment? The second paper you cite refers to the undecidability of $\exists x\in\mathbb{R}$ s.t. $E(x)=0$, while Richardsons's theorem is about $\forall x\in\mathbb{R}$ s.t. $E(x)=0$. $\endgroup$ Jul 4, 2020 at 17:16
45
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ May 25, 2010 at 4:11
  • $\begingroup$ wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/… $\endgroup$ Jul 3, 2010 at 8:26
  • 4
    $\begingroup$ 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. $\endgroup$
    – Lee Mosher
    Mar 28, 2012 at 16:35
38
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ What kind of deformation of $\mathbb{R}^{n+2}$? $\endgroup$
    – Joey Hirsh
    Jan 12, 2010 at 20:31
  • $\begingroup$ An ambient isotopy $\endgroup$
    – user1073
    Jan 12, 2010 at 20:37
  • 14
    $\begingroup$ 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. $\endgroup$ Jan 12, 2010 at 20:57
36
$\begingroup$

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 by Klaus Weihrauch for more details.)

$\endgroup$
6
  • $\begingroup$ This is very similar to the fact that the pushforward of sheaves is easier to define, but the inverse image sheaf is significantly easier to computte. $\endgroup$ Apr 25, 2010 at 15:49
  • 1
    $\begingroup$ 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_*$. $\endgroup$ Jun 24, 2010 at 19:22
  • 5
    $\begingroup$ I would expect integration to be easier than differentiation, because every computable function is continuous and every continuous function is integrable (on a compact interval). Thus to decide if a computable function is integrable is trivially computable: always return Yes. To actually calculate the integral computably is harder but seems likely to work (and I happen to know that it does). $\endgroup$ Jul 28, 2012 at 23:36
  • 2
    $\begingroup$ In contrast, not every continuous function is differentiable, so to decide if a computable function is differentiable (much less to decide if it's computably differentiable and if so to compute its derivative) might be impossible. And so it is. $\endgroup$ Jul 28, 2012 at 23:37
  • 3
    $\begingroup$ Peter -- It's true that this is not an example of an intermediate Turing degree, but it is also not a reduction to the halting problem, because the problem of verifying differentiability is much more difficult than the halting problem. Because differentiability is naively a $\Pi^1_1$ property, the problem is reducible to Kleene's O. This is optimal by a 1936 paper of Mazurkiewicz. (His argument is reproduced in Kechris and Woodin's 1986 paper "Ranks of Differentiable Functions" as the original is hard to find. The original argument was set-theoretic but it effectivizes.) $\endgroup$ Jan 10, 2014 at 4:37
33
$\begingroup$

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 https://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?

$\endgroup$
1
  • 1
    $\begingroup$ It's staggering to learn that 2 does not have an easy decision procedure! I suppose that it has to do with diophantine properties of complex PF numbers (algebraic numbers with at least one conjugate with the same absolute value and none with larger). $\endgroup$ May 25, 2010 at 4:00
29
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Nice. I like the 1-PFA problem for the same reason. $\endgroup$ Jul 2, 2010 at 9:55
  • 2
    $\begingroup$ See also my note of June 3rd on this same problem. It deserves double mention! $\endgroup$ Feb 18, 2011 at 2:00
28
$\begingroup$

Four from Compiler Science:

  1. Does a program ever access an uninitialized variable.
  2. Do two context free grammars describe the same language.
  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 problem. So the above might be considered too close the the halting problem to be interesting answers ot this question.

$\endgroup$
3
  • $\begingroup$ I don't find it a flaw to be close to or equivalent to the halting problem. After all, in a robust sense I think all the answers posted here so far are equivalent to the Halting problem, in the sense of Turing equivalence. Undecidability in the cases of the answers is established ultimately by reducing the Halting problem to the given problem, and conversely, for each problem one can reduce it to the Halting problem. So all the posted problems have the same Turing degree as the Halting Problem. $\endgroup$ Jan 13, 2010 at 13:18
  • 4
    $\begingroup$ Aren't these just special cases of Rice's Theorem? $\endgroup$ Mar 7, 2013 at 21:41
  • 5
    $\begingroup$ @Christoph - no, Rice's theorem says we cannot decide nontrivial things about a the language of a program, but #1,3,4 do not deal with the program's language and #2 does not get programs as input. $\endgroup$
    – usul
    Jun 18, 2013 at 20:47
28
$\begingroup$

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.

$\endgroup$
6
  • 4
    $\begingroup$ 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. $\endgroup$ Jan 12, 2010 at 18:53
  • 4
    $\begingroup$ 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). $\endgroup$
    – Tim Perutz
    Jan 12, 2010 at 19:16
  • $\begingroup$ Sorry, I was being very sloppy. $\endgroup$
    – S. Carnahan
    Jan 12, 2010 at 20:07
  • 8
    $\begingroup$ 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. $\endgroup$ May 24, 2010 at 22:34
  • $\begingroup$ @John Stillwell: but I guess we can see from this example that the group on the generators ‘S’, ‘P’, and ‘Novikov’ does not prove that P.S = S.P! $\endgroup$ Feb 18, 2011 at 15:36
25
$\begingroup$

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

$\endgroup$
21
$\begingroup$

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

$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$ Jan 13, 2010 at 14:34
  • 22
    $\begingroup$ @Joel This still applies for computable reals. Computable reals are finitely encodable. $\endgroup$
    – Dan Piponi
    Feb 19, 2010 at 0:11
  • $\begingroup$ Could someone add a reference for this, including Dan Piponis comment? $\endgroup$ Feb 14, 2012 at 7:52
  • 2
    $\begingroup$ Michael, you are looking for the subject known as computable analysis: en.wikipedia.org/wiki/Computable_analysis. It is an elementary argument via the recursion theorem to show that equality of computable reals is not computable; indeed, you cannot even decide if a computable number is zero. (If you have an algorithm that does decide this correctly, then design a program $p$ that pretends to be zero until your algorithm says it is zero, and then after this $p$ should make the real non-zero, a contradiction.) $\endgroup$ May 29, 2012 at 12:24
  • 1
    $\begingroup$ As Dan says, it applies to computable reals. And if you can't decide whether two computable reals are equal, then certainly you can't decide whether two arbitrary reals are equal! (This only to make the reals ‘disturbing’.) $\endgroup$ Jul 28, 2012 at 23:41
19
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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: When are (finite) simplicial complexes (smooth) manifolds?

$\endgroup$
1
  • 1
    $\begingroup$ In that case, how about "Given a 5-manifold (as a simplicial complex, say), is it the 5-sphere?"? $\endgroup$
    – HJRW
    Sep 12, 2016 at 13:07
16
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

Above it was mentioned that, from a general finite group presentation, it is not decidable whether the group is finite. There are actually 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!?

$\endgroup$
1
14
$\begingroup$

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

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 2, 2010 at 20:20
13
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$ Mar 28, 2012 at 18:29
  • 4
    $\begingroup$ 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. $\endgroup$ Mar 28, 2012 at 20:59
10
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ Statements like this do have an effect on the decidability of the Risch algorithm (en.wikipedia.org/wiki/Risch_algorithm). $\endgroup$ Jan 12, 2010 at 17:29
  • 3
    $\begingroup$ What data is given on the function? $\endgroup$ Jan 12, 2010 at 19:36
  • 2
    $\begingroup$ If you're given the Taylor expansion at the origin I'd hope it's decidable. :) $\endgroup$ Jan 12, 2010 at 19:48
  • 3
    $\begingroup$ 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! $\endgroup$ Jan 19, 2010 at 16:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – kakaz
    Feb 16, 2010 at 12:19
10
$\begingroup$

The rule 110 is also a cute one.

$\endgroup$
16
  • 1
    $\begingroup$ As well as for its own sake, I find this one intensely interesting from the non-mathematical standpoint: it's simple enough that it is quite plausible that lone molecules / simple groups of such could be working as universal Turing machines. Even more plausible when you consider that there are many such rules that are Turing complete. Mind boggling implications for biology. $\endgroup$ Jun 6, 2011 at 4:27
  • $\begingroup$ "Rule 110" is not an "undecidable problem", and the Wikipedia page does not clearly state what is an undecidable problem related to it. $\endgroup$
    – Ville Salo
    Sep 27, 2023 at 6:40
  • $\begingroup$ @VilleSalo It is of course decidable what the state will be after n steps. The Wikipedia tells that it is 'Turing Complete'. This implies that it is undecidable whether a cell will flip eventually to 1 given a certain begin state (so, not knowing the number of steps). $\endgroup$
    – Lucas K.
    Sep 28, 2023 at 8:16
  • $\begingroup$ And how do you restrict the initial state? If you just have arbitrary computable sequences, then this problem is undecidable for the shift map. Is 110 more Turing complete than a shift map? Just to clarify, I know at least one useful answer to this question, and am just pointing out that this answer is not very good as it stands. (And yes technically I could fix it, but this would take much longer than complaining.) $\endgroup$
    – Ville Salo
    Sep 28, 2023 at 10:32
  • $\begingroup$ (The downvote is not mine, and I'd love to see a precise version of this answer here.) $\endgroup$
    – Ville Salo
    Sep 28, 2023 at 10:36
8
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

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

$\endgroup$
7
$\begingroup$

In relation to the undecidability for 3x3 matrices and the answer of https://mathoverflow.net/users/1587/john-stillwell that

"The corresponding problem for 2×2 matrices is apparently still open":

There is a recent proof that the membership for non-singular 2×2 integer matrices is decidable (i.e. for 2x2 integer matrices with nonzero determinant). http://arxiv.org/abs/1604.02303

However in terms of uncedaibiltity the identity problem for 3x3 integer matrices is still open, while the general open problem about the identity matrix was proved to be undecidable for 4x4 matrices over integers , see

Paul C. Bell, Igor Potapov: On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups. Int. J. Found. Comput. Sci. 21(6): 963-978 (2010) and arxiv.org/abs/0902.1975

solving the long standing open problem see Problem 10.3 in http://press.princeton.edu/math/blondel/solutions.html Unsolved Problems in Mathematical Systems and Control. Theory, Princeton Univ. Press, 2004.

It also follows that whether a matrix semigroup is a group is undecidable for 4x4 integer matrices.

--- extra comments ------

Finally here are the comments about the importance of the are on matrix products.

Matrices and matrix products play a crucial role in the representation and analysis of various computational processes, i.e., linear recurrent sequences, arithmetic circuits, hybrid and dynamical systems, probabilistic and quantum automat, stochastic games, broadcast protocols, optical systems, etc. Many simply formulated and elementary problems for matrices are inherently difficult to solve even in dimension two, and most of these problems become undecidable in general starting from dimension three or four. One such hard question is the Membership Problem.

Even algorithmic problems for matrices over SL(2,Z) have many important complexity questions. They are appear in the context of many fundamental problems from hyperbolic geometry, dynamical systems, Lorenz/modular knots, braid groups, particle physics, high energy physics, M/string theories, ray tracing analysis, music theory, etc.

I would like to also to cite Prof. J. N. Tsitsiklis http://www.mit.edu/~jnt/complex.html from the webpage "Computational complexity in systems and control" which contains results on computational problems for matrix products:

"The subject is multifaceted and interesting in many different ways. It can help the practitioner in choosing problem formulations, and in calibrating expectations of what can be algorithmically accomplished. For the systems theorist or the applied mathematician, it raises a variety of challenging open problems that require a diverse set of tools from both discrete and continuous mathematics. Finally, for the theoretical computer scientist, the problems in systems and control theory provide the opportunity to relate abstractly defined complexity classes and specific problems of practical interest."

$\endgroup$
2
  • $\begingroup$ The audience will appreciate more if you can comment on the meaning of the decidability/undecidability of matrices, and why they are important and deep to choose as the most attractive Turing undecidable problems. $\endgroup$
    – wonderich
    Sep 10, 2016 at 17:39
  • $\begingroup$ I added some comments to the post about the importance of the complexity/decidability status for matrix problems. $\endgroup$ Sep 10, 2016 at 20:09
6
$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.