Re: Foundation for a Formal Refutation of the Original Halting Problem?

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 08/02/04 

Date: 2 Aug 2004 08:32:32 -0700

Peter Olcott says...

Peter, there is no better proof that you are an incompetent than
the fact that, after all this time, you haven't even understood
Turing's counterexample:

You wrote:

>01) int WillHalt(string SourceCode, string DataInput)
>02) {
>03) if (TheProgramHalts(SourceCode, DataInput))
>04) return 1; // also means true in C/C++
>05) else
>06) return 0; // also means false in C/C++
>07) }
>
>08) void LoopIfHalts(string SourceCode, string DataInput)
>09) {
>10) if (WillHalt(SourceCode, DataInput))
>11) while(true)
>12) ;
>13) else
>14) return;
>15) }
>
>16) cout << WillHalt(LoopIfHalts, LoopIfHalts);

That is just plain wrong. Note that LoopIfHalts takes *two*
arguments as inputs. You've only supplied *one* argument. So
running WillHalt(LoopIfHalts, LoopIfHalts) will produce an
error.

Somehow, after all this time, you *still* don't understand
Turing's proof. The way Turing's proof works is this: (reworded
to correspond to your terminology)

   WillHalt(M,x): is assumed to return "true" if M halts on input x,
                  and returns "false" otherwise

Note: this *only* makes sense if M is a program with *one* argument.
If M is a program with more than one argument (or zero arguments)
then WillHalt(M,x) is ill-defined. You can, perhaps, specify that
WillHalt(M,x) returns false or an error in that case.

To show that WillHalt can't exist, you construct a new program
LoopIfHalts(M). This program has only *one* argument (and so it
is a program that can be analyzed by WillHalt).

    LoopIfHalts(M): if WillHalt(M,M) loop forever, otherwise halt

Now, consider the two different computations:

     1. WillHalt(LoopIfHalts,LoopIfHalts)
     2. LoopIfHalts(LoopIfHalts)

By definition of WillHalt, the first computation should halt and
return true if and only if the second computation halts. But by
definition of LoopIfHalts, the second computation should halt if
and only if the first computation returns false. This is a contradiction.

Your way around this is to say that WillHalt(LoopIfHalts,LoopIfHalts)
returns one value if called from within LoopIfHalts, and returns a
different value if it is called in isolation. But that means that *one*
of those two return values is wrong. Either the value returned to
LoopIfHalts is wrong, or the value returned by WillHalt in isolation
is wrong. In either case, WillHalt must give the wrong answer in some
case, and so WillHalt is *not* a solution to the halting problem. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages