Re: Alan Turing's Halting Problem is incorrectly formed

From: Sander Bruggink (bruggink.at.phil.uu.nl_at_no.spam.please)
Date: 06/11/04 

Date: Fri, 11 Jun 2004 11:03:39 +0200

Peter Olcott wrote:
>>>This is the absurd part
>>>
>>> if (Halts(ThisProgram))
>>> while(true); // loop forever
>>
>>No, this is not a part of the halting problem. It is a part of the
>>*proof* that the halting problem is unsolvable.
>
>
> Okay fine, then the Halting Problem is solvable because the proof is flawed.
>

Do you even understand logic? Let me spell it out for you once more, in
a clear way, I hope:

(1) Assume the halting problem is solvable. Note that we do not claim
that it is solvable, we just assume it is for the sake of the argument.

(2) Since the halting problem is solvable (by assumption), there must
exist a TM HALT(M,x), which, given a (representation of a TM) M and an
input x, halts with "yes" if M halts on x, and with "no" if it does not.

(3) Given this TM HALT, we can construct a new TM D, which works like:

function D(M, x) {
   if HALT(M,x) then while(true);
                else return true;
}

Note that we can construct D *if* the TM HALT exists. If HALT does not
exist, it cannot be constructed because it calls HALT. (This is important.)

(4) But now what happens if we run D on (a representation of) itself.
Then D halts if and only if it does not halt. This, of course, is
absurd, as you note yourself.

(5) Now the important step: D obviously cannot exist (as you rightly
claimed yourself). But we can construct D if HALT exists, so HALT cannot
exist either (this is the part you seem to miss). So, there cannot exist
a TM which solves the halting problem. Conclusion: the halting problem
is unsolvable.

Where is the flaw in the proof?

groente
-- Sander

Relevant Pages

  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (comp.theory)
  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (sci.logic)
  • Re: The formal and informal proofs
    ... I am paid to formalize all day. ... > HALT(x,y) = List the TMs that halt. ... > possible, you have a formalization of the Halting Problem, the Every ...
    (sci.logic)
  • Re: A modern view of the halting problem
    ... program will halt. ... design of the language? ... The halting problem is not about stopping at specific instructions; ... using Riemann Hypothesis instead. ...
    (alt.lang.asm)
  • Re: What is the Result from Invoking this Halt Function?
    ... > produce a halt analyzer that returns a correct ... >> refute the definition of the Halting Problem ... (The problem of finding out whether a given Turing Machine ...
    (sci.logic)
Quantcast