29
$\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$
25
  • $\begingroup$ @EvilJS My understanding was that the undecidability proof there involved the ability to simulate TMs, though perhaps I'm mistaken? $\endgroup$ 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$ 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$ 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$ Dec 29 '15 at 20:48
11
+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$
8
  • $\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$ 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$
3
  • $\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$ 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
0
$\begingroup$

This is a really interesting question and I also had this question before when I learn computability theory. Here I give an alternative angle to view this question. In the following paragraphs I assume that the formal system that I use is first-order logic.

If you can prove that a problem P is undecidable, then you have at least one “proof” showing that “P is undecidable”. Since the set of all possible proofs is countable, we can conclude that the set of undecidable problems that you can formally prove the undecidability is also countable. But the set of all undecidable problems is uncountable, which means most undecidable problems cannot be proved to be undecidable at all.

On the other hand, if you can show a countably infinite set of undecidable problems where each problem’s undecidability can be proved via self-reference, you can at least show that the cardinality of the set of “provably undecidable problems” and the cardinality of the set of “undecidable problems provable by self-reference” are the same. This might not be an interesting result, but if we can go one step further and prove something like “all/almost all provably undecidable problems could be proved to be undecidable by self-reference”, I think that will be interesting enough.

Regarding specific proof techniques, I don’t know non-self-reference techniques for proving undecidability but I can make an informal argument stating that those techniques may not exist for certain undecidable problems. In program analysis, which is a research area trying to design (incomplete) analyzers to inform programs’ non-trivial properties, according to Rice’s theorem, non-trivial extensional properties of programs are undecidable. For such undecidable problems, different program analyzers give different “precisions” (e.g. the number of programs that they can precisely analyze). This might imply that the undecidability indeed depends on the analyzer itself because for a specific program, whether its property could be precisely analyzed via a given analyzer depends on the analyzer itself. As a result, I feel that a proof showing the undecidability of program analysis (the non-existence of complete program analyzers) tends to somehow mention the analyzer itself, which constitutes a “self-reference”. Of course I’m talking about the prove-by-contradiction route “assuming that a complete analyzer exists”.

$\endgroup$

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.