<p>Reposted from my comment as per request:</p>

<p>Start with the observation that there are undecidable problems (simple cardinality argument), and moreover that there is an undecidable problem P that has a TM M that recognizes its members (but may not terminate on non-members). Now, solving HALT(M) gives you a decider for P. We first check if M halts on x. If it does, we run it and return the same as M. Otherwise, we reject, since M halts on every member of P. This is now a contradiction since we assumed that P was undecidable.</p>

<p>Note: He clarified that he was looking for an argument that avoided diagonalization using HALT directly, not an argument that avoided diagonalization entirely.</p>

<p>EDIT: This argument is stuck. Can you show directly that RE - REC is non-empty, besides for showing that HALT is in there?</p>

CC BY-SA 2.5
2010-11-11T02:27:41.247Z
The countability argument uses a very similar (only slightly simpler) diagonalization than the standard proof for the halting problem.  (That is, to show that the cardinality of languages is larger than that of TMs uses diagonalization.)  :)
Joshua Grochow
CC BY-SA 2.5
2010-11-11T03:26:04.447Z
@Joshua Read the comments. I asked if he was looking for a proof that avoided diagonalization, or one that just avoided diagonalizing using HALT. He's looking for the latter.
Mark Reitblatt
CC BY-SA 2.5
2010-11-11T03:38:58.960Z
@Mark: Ah, I missed that. Thanks. +1
Joshua Grochow
CC BY-SA 2.5
2010-11-11T17:45:16.730Z
@Mark: Could you clarify something please?  You start by remarking that there is an undecidable problem P that is recognizable, and then observe that if HALT were decidable then we could construct a decider for P.  However, in the texts I have read, things are proved in the other order--the undecidability of HALT is used to demonstrate the existence of such problems P.  Can you show the existence of undecidable yet recognizable problems without using the undecidability of HALT?
Kurt
CC BY-SA 2.5
2010-11-11T19:33:00.447Z
The fact that there exists a recognizable but undecidable problem is perhaps most easily proved by showing the halting problem is such a problem, in which case you're back where you started. There are only countably many recognizable languages.
Bjørn Kjos-Hanssen
CC BY-SA 2.5
2010-11-11T19:33:58.920Z
@Kurt You can diagonalize on the recursive sets and produce a new set that can't be recursive. But, you can construct this diagonalization with 0' (HALT), which means it must be RE. This only relies on the fact that HALT is RE, not on the fact that HALT is non-recursive. The undecidability of HALT follows as an immediate corollary.
Mark Reitblatt
CC BY-SA 2.5
2010-11-11T19:40:05.723Z
@Bjørn I retract that last argument. You need 0''' to construct that set, not 0'.
Mark Reitblatt
CC BY-SA 3.0
2011-07-20T18:56:23.120Z
Why is it obvious that there's a turing machine M that recognizes the members of some undecidable problem P?
Craig Gidney
CC BY-SA 2.5
2010-11-10T21:49:47.300Z
2010-11-11T19:41:28.763Z
2010-11-11T19:41:28.763Z
Mark Reitblatt
<p>Yes, there are such proofs in computability theory (a.k.a. recursion theory).</p>

<p>You can first show that the halting problem (the set $0'$) can be used to compute a set $G\subseteq\mathbb N$ that is <em>1-generic</em> meaning that in a sense each $\Sigma^0_1$ fact about $G$ is decided by a finite prefix of $G$. Then it is easy to prove that such a set $G$ cannot be computable (i.e., decidable). </p>

<p>We could replace 1-<a href="http://en.wikipedia.org/wiki/Forcing_%28recursion_theory%29">generic</a> here by 1-random, i.e., <a href="http://en.wikipedia.org/wiki/Algorithmically_random_sequence"><em>Martin-Löf random</em></a>, for the same effect. This uses the <a href="http://en.wikipedia.org/wiki/Low_basis_theorem">Jockusch-Soare Low Basis Theorem</a>. </p>

<p>(Warning: one might consider just showing that $0&#39;$ computes <a href="http://en.wikipedia.org/wiki/Chaitin%27s_Omega">Chaitin's $\Omega$</a>, which is 1-random, but here we have to be careful about whether the proof that $\Omega$ is 1-random relies on the halting problem being undecidable! Therefore it's safer to just use the Low Basis Theorem). </p>

CC BY-SA 2.5
2010-11-10T19:38:05.247Z
Very interesting! Can you provide me with a reference or a set of keywords to search for to be able to understand it more ? Thanks a lot!
Mohammad Alaggan
CC BY-SA 2.5
2010-11-10T20:04:04.927Z
@M. Alaggan: The best reference may be the recent book by André Nies, *Computability and Randomness*, Oxford Logic Guides, Oxford University Press, 2009. There is also a Wikipedia article about the Low Basis Theorem and a Scholarpedia article about Algorithmic Randomness: http://www.scholarpedia.org/article/Algorithmic_randomness
Bjørn Kjos-Hanssen
CC BY-SA 2.5
2010-11-11T18:10:13.530Z
@M. Alaggan, It is up to you but the votes suggest that this should be the accepted answer.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-11T18:51:34.803Z
I did ask on meta (check meta.cstheory.stackexchange.com/questions/642/when-is-it-appropriate-to-change-the-accepted-answer). I know this answer is indeed great and very useful as well. I did accept the other one, however, because it was much easier for me to understand with a more intuitive approach. However, there seem to be a discussion above on its correctness (!). So if it turned out to be incorrect I'll indeed change to this answer. The confusion arose from me not being specific in the original question that I wanted to avoid diagonalization using HALT, rather than all diagonalizations.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-11T18:56:28.767Z
I am extremely confused on which one should I accept, up to this moment, as I am choosing between a outstanding great answer and an easy/intuitive answer (my background is not very solid/mature). So, please no hard feelings :) We can discuss it and reach a satisfying decision to all. Thanks.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-11T19:14:13.483Z
@M.Alaggan I think you should wait to accept an answer until we see if I can answer the objections to mine.
Mark Reitblatt
CC BY-SA 3.0
2010-11-10T19:24:23.990Z
2011-07-18T18:58:46.867Z
2011-07-18T18:58:46.867Z
Bjørn Kjos-Hanssen
<p>This is a question related to <a href="https://cstheory.stackexchange.com/questions/2815/what-do-we-know-about-restricted-versions-of-the-halting-problem">this one</a>. Putting it again in a much simpler form after a lot of discussion there, that it felt like a totally different question.</p>

<p>The classical proof of the undecidability of the halting problem depends on demonstrating a contradiction when trying to apply a hypothetical HALT decider to itself. I think that this is just denoting the impossibility of having a HALT decider that decides whether <strong>itself</strong> will halt or not, but doesn't give any information beyond that about the decidability of halting of any <strong>other</strong> cases.</p>

<p>So the question is</p>

<blockquote>
  <p>Is there a proof that the halting problem is undecidable that doesn't depend on showing that HALT can not decide itself, nor depends on the diagonalization argument ?</p>
</blockquote>

<p>Small edit: I will commit to the original phrasing of the question, which is asking for a proof that doesn't depend on diagonlization at all (rather than a just requiring it to not depend on diagonalization that depends on HALT).</p>

CC BY-SA 2.5
2010-11-10T21:06:55.040Z
Are you looking for one that doesn't depend upon a diagonalization argument, or just one that doesn't diagonalize by using HALT directly? I'm not sure if the proof Bjørn is proposing satisfies the former.
Mark Reitblatt
CC BY-SA 2.5
2010-11-10T21:23:03.343Z
@Mark: I am not sure in fact. If the diagonalization argument doesn't correspond to self-referencing, but to other aspect such as cardinality mismatch, then I would indeed hope it would give some insight on why the termination of HALT(Q) (where Q!=HALT) is undecidable.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-10T21:29:15.800Z
Well, in that case, I can give a simpler argument. Start with the observation that there are undecidable problems (simple cardinality argument), and moreover that there is an undecidable problem P that has a TM M that recognizes its members (but may not terminate on non-members). Now, solving HALT(M) gives you a decider for P. We first check if M halts on x. If it does, we run it and return the same as M. Otherwise, we reject, since M halts on every member of P. This is now a contradiction since we assumed that P was a language without a decider.
Mark Reitblatt
CC BY-SA 2.5
2010-11-10T21:31:48.147Z
That argument is actually a proof that HALT is RE-complete.
Mark Reitblatt
CC BY-SA 2.5
2010-11-10T21:47:18.003Z
Got you. If all the TMs were deciders, then HALT is trivial. If halt is non-trivial (recognizers exist), then (by contra-positive) the existence of a non-trivial HALT makes recognizer TMs deciders, which means HALT is trivial, contradiction. So such HALT can not exist for all recognizers. This is brilliant, thank you for your wonderful comment; you might want to re-post it as an answer :)
Mohammad Alaggan
CC BY-SA 2.5
2010-11-11T18:00:48.720Z
@Bjørn Yes, HALT is RE-complete, so any argument showing the existence of non-recursive RE problems implies that HALT is non-recursive. But, as I understand it, he's looking for illumination, not trying to satisfy some restrictive proof program.
Mark Reitblatt
CC BY-SA 2.5
2010-11-11T22:11:49.277Z
I would say there's no diagonalization in my answer, since for instance the 1-generic set differs from the $e$th computable set on an input that cannot be predicted (in particular, is usually not $e$).
Bjørn Kjos-Hanssen
<computability><lo.logic><proofs>
Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?
Mohammad Alaggan
# Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

(Asked by: username_0 on 2010-11-10)

This is a question related to [this one](https://cstheory.stackexchange.com/questions/2815/what-do-we-know-about-restricted-versions-of-the-halting-problem). Putting it again in a much simpler form after a lot of discussion there, that it felt like a totally different question.

The classical proof of the undecidability of the halting problem depends on demonstrating a contradiction when trying to apply a hypothetical HALT decider to itself. I think that this is just denoting the impossibility of having a HALT decider that decides whether **itself** will halt or not, but doesn't give any information beyond that about the decidability of halting of any **other** cases.

So the question is

> Is there a proof that the halting problem is undecidable that doesn't depend on showing that HALT can not decide itself, nor depends on the diagonalization argument ?

Small edit: I will commit to the original phrasing of the question, which is asking for a proof that doesn't depend on diagonlization at all (rather than a just requiring it to not depend on diagonalization that depends on HALT).

**Tags:** computability, lo.logic, proofs
> **Comments:**
> **username_1**: Are you looking for one that doesn't depend upon a diagonalization argument, or just one that doesn't diagonalize by using HALT directly? I'm not sure if the proof Bjørn is proposing satisfies the former.  
> **username_0**: @Mark: I am not sure in fact. If the diagonalization argument doesn't correspond to self-referencing, but to other aspect such as cardinality mismatch, then I would indeed hope it would give some insight on why the termination of HALT(Q) (where Q!=HALT) is undecidable.  
> **username_1**: Well, in that case, I can give a simpler argument. Start with the observation that there are undecidable problems (simple cardinality argument), and moreover that there is an undecidable problem P that has a TM M that recognizes its members (but may not terminate on non-members). Now, solving HALT(M) gives you a decider for P. We first check if M halts on x. If it does, we run it and return the same as M. Otherwise, we reject, since M halts on every member of P. This is now a contradiction since we assumed that P was a language without a decider.  
> **username_1**: That argument is actually a proof that HALT is RE-complete.  
> **username_0**: Got you. If all the TMs were deciders, then HALT is trivial. If halt is non-trivial (recognizers exist), then (by contra-positive) the existence of a non-trivial HALT makes recognizer TMs deciders, which means HALT is trivial, contradiction. So such HALT can not exist for all recognizers. This is brilliant, thank you for your wonderful comment; you might want to re-post it as an answer :)  
> **username_1**: @Bjørn Yes, HALT is RE-complete, so any argument showing the existence of non-recursive RE problems implies that HALT is non-recursive. But, as I understand it, he's looking for illumination, not trying to satisfy some restrictive proof program.  
> **username_2**: I would say there's no diagonalization in my answer, since for instance the 1-generic set differs from the $e$th computable set on an input that cannot be predicted (in particular, is usually not $e$).  

---

## 2 answers

### Answer by username_2 on 2010-11-10. Score: 33 | Accepted answer

Yes, there are such proofs in computability theory (a.k.a. recursion theory).

You can first show that the halting problem (the set $0'$) can be used to compute a set $G\subseteq\mathbb N$ that is *1-generic* meaning that in a sense each $\Sigma^0\_1$ fact about $G$ is decided by a finite prefix of $G$. Then it is easy to prove that such a set $G$ cannot be computable (i.e., decidable).

We could replace 1-[generic](http://en.wikipedia.org/wiki/Forcing_%28recursion_theory%29) here by 1-random, i.e., [*Martin-Löf random*](http://en.wikipedia.org/wiki/Algorithmically_random_sequence), for the same effect. This uses the [Jockusch-Soare Low Basis Theorem](http://en.wikipedia.org/wiki/Low_basis_theorem).

(Warning: one might consider just showing that $0'$ computes [Chaitin's $\Omega$](http://en.wikipedia.org/wiki/Chaitin%27s_Omega), which is 1-random, but here we have to be careful about whether the proof that $\Omega$ is 1-random relies on the halting problem being undecidable! Therefore it's safer to just use the Low Basis Theorem).

> **Comments:**
> **username_0**: Very interesting! Can you provide me with a reference or a set of keywords to search for to be able to understand it more ? Thanks a lot!  
> **username_2**: @M. Alaggan: The best reference may be the recent book by André Nies, *Computability and Randomness*, Oxford Logic Guides, Oxford University Press, 2009. There is also a Wikipedia article about the Low Basis Theorem and a Scholarpedia article about Algorithmic Randomness: http://www.scholarpedia.org/article/Algorithmic_randomness  
> **username_6**: @M. Alaggan, It is up to you but the votes suggest that this should be the accepted answer.  
> **username_0**: I did ask on meta (check meta.cstheory.stackexchange.com/questions/642/when-is-it-appropriate-to-change-the-accepted-answer). I know this answer is indeed great and very useful as well. I did accept the other one, however, because it was much easier for me to understand with a more intuitive approach. However, there seem to be a discussion above on its correctness (!). So if it turned out to be incorrect I'll indeed change to this answer. The confusion arose from me not being specific in the original question that I wanted to avoid diagonalization using HALT, rather than all diagonalizations.  
> **username_0**: I am extremely confused on which one should I accept, up to this moment, as I am choosing between a outstanding great answer and an easy/intuitive answer (my background is not very solid/mature). So, please no hard feelings :) We can discuss it and reach a satisfying decision to all. Thanks.  
> **username_1**: @M.Alaggan I think you should wait to accept an answer until we see if I can answer the objections to mine.  

---

### Answer by username_1 on 2010-11-10. Score: 4

Reposted from my comment as per request:

Start with the observation that there are undecidable problems (simple cardinality argument), and moreover that there is an undecidable problem P that has a TM M that recognizes its members (but may not terminate on non-members). Now, solving HALT(M) gives you a decider for P. We first check if M halts on x. If it does, we run it and return the same as M. Otherwise, we reject, since M halts on every member of P. This is now a contradiction since we assumed that P was undecidable.

Note: He clarified that he was looking for an argument that avoided diagonalization using HALT directly, not an argument that avoided diagonalization entirely.

EDIT: This argument is stuck. Can you show directly that RE - REC is non-empty, besides for showing that HALT is in there?

> **Comments:**
> **username_3**: The countability argument uses a very similar (only slightly simpler) diagonalization than the standard proof for the halting problem.  (That is, to show that the cardinality of languages is larger than that of TMs uses diagonalization.)  :)  
> **username_1**: @Joshua Read the comments. I asked if he was looking for a proof that avoided diagonalization, or one that just avoided diagonalizing using HALT. He's looking for the latter.  
> **username_3**: @Mark: Ah, I missed that. Thanks. +1  
> **username_4**: @Mark: Could you clarify something please?  You start by remarking that there is an undecidable problem P that is recognizable, and then observe that if HALT were decidable then we could construct a decider for P.  However, in the texts I have read, things are proved in the other order--the undecidability of HALT is used to demonstrate the existence of such problems P.  Can you show the existence of undecidable yet recognizable problems without using the undecidability of HALT?  
> **username_2**: The fact that there exists a recognizable but undecidable problem is perhaps most easily proved by showing the halting problem is such a problem, in which case you're back where you started. There are only countably many recognizable languages.  
> **username_1**: @Kurt You can diagonalize on the recursive sets and produce a new set that can't be recursive. But, you can construct this diagonalization with 0' (HALT), which means it must be RE. This only relies on the fact that HALT is RE, not on the fact that HALT is non-recursive. The undecidability of HALT follows as an immediate corollary.  
> **username_1**: @Bjørn I retract that last argument. You need 0''' to construct that set, not 0'.  
> **username_5**: Why is it obvious that there's a turing machine M that recognizes the members of some undecidable problem P?  

---

