<p>Consider what I like to call the CONSISTENT GUESSING problem.</p>

<p>Given as input a description of a Turing machine $M$:</p>

<ul>
<li><p>If $M$ accepts on a blank tape, you have to accept.</p></li>
<li><p>If $M$ rejects on a blank tape, you have to reject.</p></li>
<li><p>If $M$ runs forever on a blank tape, then you can either accept or reject, but in either case you have to halt.</p></li>
</ul>

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

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

<p>On the other hand, it's also possible to show that there's <i>no</i> 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.</p>

CC BY-SA 3.0
2014-04-04T20:56:56.963Z
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...
David Monniaux
CC BY-SA 3.0
2014-04-05T23:12:37.167Z
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](http://www.seas.upenn.edu/~sweirich/types/archive/1989/msg00093.html) or [matrix reachability](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.9129))
cody
CC BY-SA 3.0
2014-04-07T12:56:39.470Z
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.)
Scott Aaronson
CC BY-SA 3.0
2014-04-04T20:41:06.527Z
2014-04-04T20:41:06.527Z
Scott Aaronson
<p>One can show fairly directly that Kolmogorov complexity is not computable, see e.g. Sipser, 3rd edition, problem  6.23.</p>

CC BY-SA 3.0
2014-04-04T02:31:58.613Z
This should also follow directly from [Chaitin's incompleteness theorem](http://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin.27s_incompleteness_theorem), whose proof is quite similar.
Yonatan N
CC BY-SA 3.0
2014-04-04T03:16:03.440Z
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.
usul
CC BY-SA 3.0
2014-04-04T03:40:58.203Z
Actually comparing to Exercises 6.24 and 6.25 also helps.
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2014-04-04T05:00:30.913Z
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...
Joshua Grochow
CC BY-SA 3.0
2014-04-04T02:27:36.103Z
2014-04-04T02:39:46.727Z
2014-04-04T02:39:46.727Z
Bjørn Kjos-Hanssen
<p>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. </p>

<p>And all of those diagonalizations are <em>essentially the same proof</em>. 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.)</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-05T05:38:07.833Z
I don't know much that topic, but isn't Lawvere's fixed point theorem a common generalization of almost all of these?
Sasho Nikolov
CC BY-SA 3.0
2014-04-05T04:41:34.683Z
2014-04-05T04:41:34.683Z
Joshua Grochow
<p>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.</p>

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

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

CC BY-SA 3.0
2014-04-03T18:19:03.837Z
Maybe the right question is: "what are the different **direct** methods to prove undecidability" ?
Suresh Venkat
CC BY-SA 3.0
2014-04-03T18:27:22.477Z
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](http://cstheory.stackexchange.com/questions/10635/halting-problem-uncomputable-sets-common-mathematical-proof)
vzn
CC BY-SA 3.0
2014-04-04T00:56:22.340Z
Possible duplicate: [Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization?](http://cstheory.stackexchange.com/q/2853/186)
Kaveh
CC BY-SA 3.0
2014-04-04T02:47:40.470Z
@vzn: I think of Godel incompleteness as essentially the same proof...
Joshua Grochow
CC BY-SA 3.0
2014-04-04T22:51:33.473Z
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](http://en.wikipedia.org/wiki/List_of_undecidable_problems) 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.
Marzio De Biasi
CC BY-SA 3.0
2014-04-05T05:10:36.260Z
Existence of certain classes of inductive invariants (e.g. convex polyhedra) separating initial from final states for certain classes of transition relations (e.g. Presburger arithmetic). If the class is rich enough, one can reduce Hilbert's Xth problem or the halting problem to it, but in general... (Note: some subclasses are known to be decidable, e.g. \Sigma^p_2-complete, or in NEXPTIME and EXPTIME-hard.)
David Monniaux
<computability>
Proof of undecidability not by reduction from the halting problem
David Monniaux
# Proof of undecidability not by reduction from the halting problem

(Asked by: username_0 on 2014-04-03)

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?

**Tags:** computability
> **Comments:**
> **username_1**: Maybe the right question is: "what are the different **direct** methods to prove undecidability" ?  
> **username_2**: 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](http://cstheory.stackexchange.com/questions/10635/halting-problem-uncomputable-sets-common-mathematical-proof)  
> **username_3**: Possible duplicate: [Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization?](http://cstheory.stackexchange.com/q/2853/186)  
> **username_4**: @vzn: I think of Godel incompleteness as essentially the same proof...  
> **username_5**: 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](http://en.wikipedia.org/wiki/List_of_undecidable_problems) 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.  
> **username_0**: Existence of certain classes of inductive invariants (e.g. convex polyhedra) separating initial from final states for certain classes of transition relations (e.g. Presburger arithmetic). If the class is rich enough, one can reduce Hilbert's Xth problem or the halting problem to it, but in general... (Note: some subclasses are known to be decidable, e.g. \Sigma^p_2-complete, or in NEXPTIME and EXPTIME-hard.)  

---

## 3 answers

### Answer by username_6 on 2014-04-04. Score: 12

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.

> **Comments:**
> **username_0**: 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...  
> **username_7**: 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](http://www.seas.upenn.edu/~sweirich/types/archive/1989/msg00093.html) or [matrix reachability](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.154.9129))  
> **username_6**: 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.)  

---

### Answer by username_8 on 2014-04-04. Score: 10

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

> **Comments:**
> **username_9**: This should also follow directly from [Chaitin's incompleteness theorem](http://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin.27s_incompleteness_theorem), whose proof is quite similar.  
> **username_10**: 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.  
> **username_8**: Actually comparing to Exercises 6.24 and 6.25 also helps.  
> **username_4**: 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...  

---

### Answer by username_4 on 2014-04-05. Score: 5

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.

> **Comments:**
> **username_11**: I don't know much that topic, but isn't Lawvere's fixed point theorem a common generalization of almost all of these?  

---

