14
$\begingroup$

The usual way of proving undecidability is by reduction from a RE-complete problem such as the halting problem, validity in first order logic, satisfiability of Diophantine equations, etc.

It is known that there are recursively enumerable, but undecidable problems that are not RE-complete, but these are artificial constructions (that is, sets that have been defined just for showing this "density" result).

How would one tackle proving undecidability without reduction from a RE-complete problem? Diagonalization?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ Maybe the right question is: "what are the different direct methods to prove undecidability" ? $\endgroup$
    – Suresh Venkat
    Commented Apr 3, 2014 at 18:19
  • $\begingroup$ the Godel incompleteness theorem is seen somewhat to be a "different way"... another diagonalization proof relies on that the # of programs/input pairs is countable but languages are uncountable, and so in this way is similar to the incommensurability of the reals with the integers. see also this Q/A re Lawvere fixed point theorem $\endgroup$
    – vzn
    Commented Apr 3, 2014 at 18:27
  • 5
    $\begingroup$ Possible duplicate: Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization? $\endgroup$
    – Kaveh
    Commented Apr 4, 2014 at 0:56
  • 6
    $\begingroup$ @vzn: I think of Godel incompleteness as essentially the same proof... $\endgroup$
    – Joshua Grochow
    Commented Apr 4, 2014 at 2:47
  • $\begingroup$ Just for curiosity, for what kind of problem or language are you trying to prove undecidability? I think that there are many known undecidable problems (see for example a small list on Wikipedia) that you can reduce from, so I'm wondering if at least one of them is similar to yours or if it is a completely new problem. $\endgroup$
    – Marzio De Biasi
    Commented Apr 4, 2014 at 22:51

3 Answers 3

Reset to default
12
$\begingroup$

Consider what I like to call the CONSISTENT GUESSING problem.

Given as input a description of a Turing machine $M$:

  • If $M$ accepts on a blank tape, you have to accept.

  • If $M$ rejects on a blank tape, you have to reject.

  • If $M$ runs forever on a blank tape, then you can either accept or reject, but in either case you have to halt.

(Of course this isn't quite a language, but more like a computability analogue of a promise problem.)

Now, by a modification of Turing's original proof, it's quite easy to show that CONSISTENT GUESSING is undecidable (I'll leave that as an exercise for you).

On the other hand, it's also possible to show that there's no reduction from the halting problem to CONSISTENT GUESSING---i.e., that it's possible to construct an oracle $A$ that returns the correct accept/reject answer for every halting TM, but whose answers for the non-halting TMs kill off every possible reduction from the halting problem to $A$. Thus, CONSISTENT GUESSING should really be seen as intermediate in difficulty between computable and the halting problem.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, but... again, a diagonalization proof. ;-) My problem is that I have something which I think is undecidable (basically, for 35+ years, people have always looked for heuristic algorithms or algorithms valid for subclasses to solve it) but for which there seem to be neither "obvious" reductions from r.e. nor some nice diagonalization argument... $\endgroup$
    – David Monniaux
    Commented Apr 4, 2014 at 20:56
  • $\begingroup$ Note that there are no "natural" problems which are known to be undecidable but don't have a (known) Turing reduction to the halting problem. In particular, the only "recommended" approach to show that something is undecidable is to reduce it to another undecidable problem (e.g. semi-unification or matrix reachability) $\endgroup$
    – cody
    Commented Apr 5, 2014 at 23:12
  • $\begingroup$ cody: That's what I used to think, too. But if you're willing to consider more general tasks than deciding a language, then CONSISTENT GUESSING is a pretty natural counterexample! (Incidentally, I assume you meant, reducing the known undecidable problems to your problem, rather than the other way around.) $\endgroup$
    – Scott Aaronson
    Commented Apr 7, 2014 at 12:56
10
$\begingroup$

One can show fairly directly that Kolmogorov complexity is not computable, see e.g. Sipser, 3rd edition, problem 6.23.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This should also follow directly from Chaitin's incompleteness theorem, whose proof is quite similar. $\endgroup$
    – Yonatan N
    Commented Apr 4, 2014 at 2:31
  • $\begingroup$ It seems to me from the previous problems that Sipser intends students to use the undecidability of the halting problem for this proof, so maybe it is worth sketching the direct proof of uncomputability in the answer. $\endgroup$
    – usul
    Commented Apr 4, 2014 at 3:16
  • $\begingroup$ Actually comparing to Exercises 6.24 and 6.25 also helps. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Apr 4, 2014 at 3:40
  • 2
    $\begingroup$ I thought it might be worth pointing out - given that the OQ asked specifically about diagonalization - that the proof that K is uncomputable is also essentially diagonalization. (Indeed, it's basically the same, plain-vanilla diagonalization that's used to prove HALT uncomputable, which is the same as Cantor's original proof about cardinalities, which is the same as the proofs of Godel and Chaitin incompleteness, which are the all just theorem-versions of Russell's paradox... $\endgroup$
    – Joshua Grochow
    Commented Apr 4, 2014 at 5:00
5
$\begingroup$

If what you're looking for is a proof that is neither a) reduction from a known complete problem, nor b) straightforward diagonalization (which your various comments indicate you are), then as far as I know you are out of luck. All of the proofs that I am aware of that aren't by reduction - including those in the other excellent answers given here by Aaronson and Kjos-Hanssen - proceed by straightforward diagonalization.

And all of those diagonalizations are essentially the same proof. Some of them are slight variants on the proof that yield slightly stronger/weaker statements, but the proofs themselves are typically just very slight variations. (And all of these proofs are essentially the same as Cantor's original proof about cardinalities, which is the same as the proofs of Godel and Chaitin incompleteness, which are the all just theorem-versions of Russell's paradox... So much so that at one point I wondered if one could formalize in some sort of reverse-mathematics kind of way a theorem which said that there was essentially only one such proof.)

It may be worth pointing out, however, that there are proofs of other statements - typically of a different flavor - that are diagonalizations that are really, truly, provably different than diagonalization used to prove e.g. undecidability of the halting problem.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ I don't know much that topic, but isn't Lawvere's fixed point theorem a common generalization of almost all of these? $\endgroup$
    – Sasho Nikolov
    Commented Apr 5, 2014 at 5:38

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.