46

This is a question related to this one. 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).

Community
  • 1
Mohammad Alaggan
  • 1,812
  • 18
  • 29
  • 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 Nov 10 '10 at 21:06
  • @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 Nov 10 '10 at 21:23
  • 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. – Mark Reitblatt Nov 10 '10 at 21:29
  • That argument is actually a proof that HALT is RE-complete. – Mark Reitblatt Nov 10 '10 at 21:31
  • 1
    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 Nov 10 '10 at 21:47
  • @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 Nov 11 '10 at 18:00
  • 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 Nov 11 '10 at 22:11

4 Answers4

33

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 here by 1-random, i.e., Martin-Löf random, for the same effect. This uses the Jockusch-Soare Low Basis Theorem.

(Warning: one might consider just showing that $0'$ computes Chaitin's $\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).

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Bjørn Kjos-Hanssen
  • 4,485
  • 2
  • 25
  • 40
  • 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 Nov 10 '10 at 19:38
  • 6
    @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 Nov 10 '10 at 20:04
  • @M. Alaggan, It is up to you but the votes suggest that this should be the accepted answer. – Mohammad Al-Turkistany Nov 11 '10 at 18:10
  • 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 Nov 11 '10 at 18:51
  • 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 Nov 11 '10 at 18:56
  • @M.Alaggan I think you should wait to accept an answer until we see if I can answer the objections to mine. – Mark Reitblatt Nov 11 '10 at 19:14
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?

Mark Reitblatt
  • 1,690
  • 15
  • 20
  • 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 Nov 11 '10 at 02:27
  • @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 Nov 11 '10 at 03:26
  • @Mark: Ah, I missed that. Thanks. +1 – Joshua Grochow Nov 11 '10 at 03:38
  • 5
    @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 Nov 11 '10 at 17:45
  • 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. – Bjørn Kjos-Hanssen Nov 11 '10 at 19:33
  • @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 Nov 11 '10 at 19:33
  • @Bjørn I retract that last argument. You need 0''' to construct that set, not 0'. – Mark Reitblatt Nov 11 '10 at 19:40
  • 1
    Why is it obvious that there's a turing machine M that recognizes the members of some undecidable problem P? – Craig Gidney Jul 20 '11 at 18:56
3

Another poster alluded to this (by referring to Chaitin), but you can use the Berry paradox to prove that the halting problem is undecidable. Here is a brief sketch of the proof:

Let HALT be a machine that decides if any machine M halts on input I. We will demonstrate that HALT itself fails to halt on a particular input, which shows that it is unable to decide the language.

Consider the following function f:

f(M, n) = a, where a is the smallest positive integer not computable by machine M on any input I with |I| < n

Assuming that HALT is a computable function, f is also a computable function; simply simulate HALT(M,I) for every machine M and input string I with the length of I less than n. If the simulation halts, then simulate M(I) and record what the output is, and find the smallest output a that is not outputted by any of the M,n pairs.

Now, we show that f is not computable: consider f(f, 10000000*|f|+10000000). Whatever it outputs, it ought to be a (positive) integer that is not computable by the machine computing f on input I with length less than that given...and yet we've just outputted such an integer with f and a much briefer input.

Thus, f is not computable, and so our assumption that HALT was computable is false. I do not believe this proof makes any use of diagonalization.

  • This proof is invalid. Whatever it outputs, it ought to be an integer that is not computable by the machine computing f on input I with length less than that given. An appeal to modular arithmetic shows this to be trivially false. The error is in assuming the machine must be capable of representing $>n$ sized numbers in order to be able to perform arithmetic on them when in fact it is possible to perform arithmetic modulo $n$. – johne Dec 16 '10 at 19:03
  • 6
    I'm not trying to be rude, but your objection makes no sense. The function f is defined as a function that outputs an integer that can't be computed by M on any input with length less than n. Thus, nonsensical appeals to modular arithmetic aside, you're going to have a difficult time showing that the sentence you highlighted is invalid. –  Dec 16 '10 at 19:48
  • @johne I concur with Philip. There is no assumption on the limits of the machine's representation. This is a TM. – Mark Reitblatt Dec 16 '10 at 22:00
  • @Philip Minor technical correction: you should change integer to natural or positive integer. – Mark Reitblatt Dec 16 '10 at 22:01
  • @Mark Reitblatt: Thank you, I've made the correction. –  Dec 16 '10 at 22:04
  • 1
    @Philip you are diagonalizing on $f$, it's just a different $f$ from the classical proof – Mark Reitblatt Dec 16 '10 at 22:36
  • Hmmm...are you sure? I might be confused about what exactly the definition of "diagonalization" is. I had read that Boolos claimed that he had given a proof of Godel's Incompleteness theorems that didn't use diagonalization by using the Berry paradox. Anyway, if this is diagonalization, what is the diagonal? I agree that they proof may be relativizizing, but I had thought that to qualify as actual diagonalization you would have to use different logic. –  Dec 16 '10 at 22:44
0

Not sure if this counts, but you can prove it using the Recursion Theorem. The recursion theorem says if $\{W_e\}_{e=1}^{\infty}$ is an effective listing of all turing machines and $f$ is a recursive function, then there is an $e$ such that $W_e = W_{f(e)}$ on all inputs. If you could decide whether or not a given machine halts on say input $0$ then you could write a recursive $f$ that, on input $e$, outputs the index of a Turing machine that halts on $0$ iff $W_e$ doesn't halt on $0$. By the recursion theorem there exists $e$ such that $W_e(0)$ = $W_{f(e)}(0)$ which is a contradiction.