45
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Mark Reitblatt
    Commented Nov 10, 2010 at 21:06
  • $\begingroup$ @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. $\endgroup$
    – Mohammad Alaggan
    Commented Nov 10, 2010 at 21:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark Reitblatt
    Commented Nov 10, 2010 at 21:29
  • $\begingroup$ That argument is actually a proof that HALT is RE-complete. $\endgroup$
    – Mark Reitblatt
    Commented Nov 10, 2010 at 21:31
  • 1
    $\begingroup$ 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 :) $\endgroup$
    – Mohammad Alaggan
    Commented Nov 10, 2010 at 21:47

4 Answers 4

Reset to default
33
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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! $\endgroup$
    – Mohammad Alaggan
    Commented Nov 10, 2010 at 19:38
  • 6
    $\begingroup$ @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: scholarpedia.org/article/Algorithmic_randomness $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Nov 10, 2010 at 20:04
  • $\begingroup$ @M. Alaggan, It is up to you but the votes suggest that this should be the accepted answer. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 11, 2010 at 18:10
  • $\begingroup$ 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. $\endgroup$
    – Mohammad Alaggan
    Commented Nov 11, 2010 at 18:51
  • $\begingroup$ 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. $\endgroup$
    – Mohammad Alaggan
    Commented Nov 11, 2010 at 18:56
4
$\begingroup$

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?

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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.) :) $\endgroup$
    – Joshua Grochow
    Commented Nov 11, 2010 at 2:27
  • $\begingroup$ @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. $\endgroup$
    – Mark Reitblatt
    Commented Nov 11, 2010 at 3:26
  • 5
    $\begingroup$ @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? $\endgroup$
    – Kurt
    Commented Nov 11, 2010 at 17:45
  • 2
    $\begingroup$ 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. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Nov 11, 2010 at 19:33
  • 1
    $\begingroup$ Why is it obvious that there's a turing machine M that recognizes the members of some undecidable problem P? $\endgroup$
    – Craig Gidney
    Commented Jul 20, 2011 at 18:56
3
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$
    – johne
    Commented Dec 16, 2010 at 19:03
  • 6
    $\begingroup$ 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. $\endgroup$
    – user1338
    Commented Dec 16, 2010 at 19:48
  • $\begingroup$ @johne I concur with Philip. There is no assumption on the limits of the machine's representation. This is a TM. $\endgroup$
    – Mark Reitblatt
    Commented Dec 16, 2010 at 22:00
  • $\begingroup$ @Philip Minor technical correction: you should change integer to natural or positive integer. $\endgroup$
    – Mark Reitblatt
    Commented Dec 16, 2010 at 22:01
  • 1
    $\begingroup$ @Philip you are diagonalizing on $f$, it's just a different $f$ from the classical proof $\endgroup$
    – Mark Reitblatt
    Commented Dec 16, 2010 at 22:36
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ This is the standard diagonalization proof. $\endgroup$
    – Yuval Filmus
    Commented Nov 11, 2010 at 23:07

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.