28
$\begingroup$

Every undecidable problem that I know of falls into one of the following categories:

  1. Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the halting problem, are undecidable because you could use a purported decider for the language to construct a TM whose behavior leads to a contradiction. You could also lump many undecidable problems about Kolmogorov complexity into this camp.

  2. Problems that are undecidable due to direct self-reference. For example, the universal language can be shown to be undecidable for the following reason: if it were decidable, then it would be possible to use Kleene's recursion theorem to build a TM that gets its own encoding, ask whether it will accept its own input, then does the opposite.

  3. Problems that are undecidable due to reductions from existing undecidable problems. Good examples here include the Post Correspondence Problem (reduction from the halting problem) and the Entscheidungsproblem.

When I teach computability theory to my students, many students pick up on this as well and often ask me if there are any problems we can prove are undecidable without ultimately tracing back to some kind of self-reference trickery. I can prove nonconstructively that there are infinitely many undecidable problems by a simple cardinality argument relating the number of TMs to the number of languages, but this doesn't give a specific example of an undecidable language.

Are there any languages known to be undecidable for reasons that aren't listed above? If so, what are they and what techniques were used to show their undecidability?

$\endgroup$
  • $\begingroup$ @EvilJS My understanding was that the undecidability proof there involved the ability to simulate TMs, though perhaps I'm mistaken? $\endgroup$ – templatetypedef Dec 26 '15 at 22:28
  • $\begingroup$ You can say Rice's theorem might not fit into any of these categories, but the proof of the theorem does. $\endgroup$ – Ryan Dec 27 '15 at 2:07
  • 1
    $\begingroup$ @EvilJS That's a good point. Really, what I'm looking for here is whether there is some fundamentally different technique we can use. It would be nice, for example, if someone identified a problem as undecidable in a case where that problem has no known relation to TM self-reference or a Godeling-type argument. If the best we can do is "we figured this one out a long time ago, then realized that it's easier to prove it another way," that in a sense would be an answer - the three techniques above fundamentally account for all the proofs of undecidability we know of. $\endgroup$ – templatetypedef Dec 28 '15 at 22:22
  • 2
    $\begingroup$ The busy beaver function grows too fast for any program to compute. Concretely, you can define a function $f(n)$ as one plus the largest number computed by a program of length at most $n$. Does that count as diagonalization? $\endgroup$ – Yuval Filmus Dec 29 '15 at 20:29
  • 1
    $\begingroup$ @YuvalFilmus Perhaps I'm being too strict here, but that sounds like a diagonal-type argument to me: you're constructing a function that is defined to be different from all functions computed by TMs. $\endgroup$ – templatetypedef Dec 29 '15 at 20:48
10
+300
$\begingroup$

Yes, there are such proofs. They are based on the Low Basis Theorem.

See this answer to Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization? question on cstheory for more.

$\endgroup$
  • $\begingroup$ If anyone is interested in advanced techniques in computability theory then check out Robert I. Soare's books Recursively Enumerable Sets and Degrees and Computability Theory and Applications. $\endgroup$ – Kaveh Jan 3 '16 at 10:42
  • $\begingroup$ Correct me if I'm wrong, but doesn't the proof of the low basis theorem involve applying a functional to itself and asking whether it doesn't produce a value? If so, isn't this just a layer of indirection on top of a diagonal argument? $\endgroup$ – templatetypedef Jan 3 '16 at 18:58
  • $\begingroup$ @templatetypedef, I am not an expert but as far as I understand no. See e.g. page 109 in Soare's book. $\endgroup$ – Kaveh Jan 3 '16 at 19:02
  • $\begingroup$ @templatetypedef, ps1: there is some vagueness in the question about what we consider diagonalization. If we are not careful we may expand what we consider to be diagonalization every time we see something which was not. Take e.g. priority methods or any general method of constructing objects part by part in a way to avoid being equal to any object from a given class. $\endgroup$ – Kaveh Jan 3 '16 at 19:21
  • 2
    $\begingroup$ @David, :) I open the page from the book I want to share, click on the share button on top, and remove the parameters except the id and pg from the link. $\endgroup$ – Kaveh Jan 3 '16 at 20:35
0
$\begingroup$

this is not exactly an affirmative answer, but an attempt at something nearby to what is asked for via a creative angle. there are quite a few problems in physics now that are "far distant" from mathematical/ theoretical formulations of undecidability, and they seem increasingly "remote" from and "bear little resemblance to" the original formulations involving the halting problem etc.; of course they use the halting problem at the root but the chains of reasoning have become increasingly distant and also have a strong "applied" aspect/ nature. unfortunately there do not seem to be any great surveys in this area yet. a recent problem that was "surprisingly" proven undecidable in physics that has attracted a lot of attention:

The spectral gap—the energy difference between the ground state and first excited state of a system—is central to quantum many-body physics. Many challenging open problems, such as the Haldane conjecture, the question of the existence of gapped topological spin liquid phases, and the Yang–Mills gap conjecture, concern spectral gaps. These and other problems are particular cases of the general spectral gap problem: given the Hamiltonian of a quantum many-body system, is it gapped or gapless? Here we prove that this is an undecidable problem. Specifically, we construct families of quantum spin systems on a two-dimensional lattice with translationally invariant, nearest-neighbour interactions, for which the spectral gap problem is undecidable. This result extends to undecidability of other low-energy properties, such as the existence of algebraically decaying ground-state correlations.

what you seem to be observing in the question is that (informally) undecidability proofs all have a certain "self-referential" structure, and this has been formally proven in even more advanced mathematics, such that both the Turing halting problem and Godels theorem can be seen as instances of the same underlying phenomenon. see eg:

The halting theorem, Cantor's theorem (the non-isomorphism of a set and its powerset), and Goedel's incompleteness theorem are all instances of the Lawvere fixed point theorem, which says that for any cartesian closed category, if there is an epimorphic map e:A→(A⇒B) then every f:B→B has a fixed point.

there is also a long meditation on this theme of the (intrinsic?) interconnectedness of self-referentiality and undecidability in the books by Hofstadter. another area where undecidability results are common and were initially somewhat "surprising" is with fractal phenomena. the crosscutting appearance/ significance of undecidable phenomena across nature is nearly a recognized physical principle at this point, first observed by Wolfram as "principle of computational equivalence".

$\endgroup$
  • $\begingroup$ other "surprising/ applied" areas of undecidability: aperiodic tilings, eventual stabilization in conway game of Life (cellular automata) $\endgroup$ – vzn Dec 29 '15 at 22:47
  • 3
    $\begingroup$ My understanding is that the proofs that all of these problems are undecidable all boil down to reductions from the halting problem. Is that incorrect? $\endgroup$ – templatetypedef Dec 29 '15 at 23:45
  • $\begingroup$ the answer basically concedes that (all known undecidability results can be reduced to the halting problem). your question is nearly phrased as a conjecture, and am not aware of any conflicting knowledge to it, and see a lot of circumstantial evidence in favor of it. but the closest to a formal proof known is apparently the fixed-point formulations of undecidability (there does not seem to be other formal formulations of "self-referential".) another way of saying it all is that Turing completeness and undecidability are two views of essentially the same phenomenon. $\endgroup$ – vzn Dec 30 '15 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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