Re: Disproof of the Halting Problem's Conclusion

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 07/25/04 

Date: Sun, 25 Jul 2004 17:09:13 GMT

"Isaac To" <iketo2@netscape.net> wrote in message news:87d62k848j.fsf@sinken.local.csis.hku.hk...
> >>>>> "Peter" == Peter Olcott <olcott@worldnet.att.net> writes:
>
> Peter> I have shown that these two functions have entirely
> Peter> different behavior by using a line-by-line execution trace.
>
> >> No, you didn't.
>
> Peter> Then you provide a line-by-line execution trace proving
> Peter> that both of these functions derive results that have the
> Peter> same semantic meaning. (How are you going to weasel out of
> Peter> that one?)
>
> Okay, I break my promise. But I promise that this is really my last
> try to teach you. You requested for a step-by-step proof, so here it
> is.

THAT IS NOT AT ALL WHAT I ASKED FOR !!!
Don't try to weasel out of it by generalizing the specifics. I provided a
line-by-line execution trace of a specific counter-example proving you wrong.

You provide me another different line-by-line execution trace of this
exact same example. Here is a simplified version that I saved. Try and
show that my conclusions for Lines 23, 24,and 25 are incorrect for this
exact and precise example. Don't try and weasel out of it again by
resorting to generalities, or any other means.

Line 01) void LoopIfHalts(string SourceCode, string InputData)
Line 02) {
Line 03) if (WillHalt(SourceCode, InputData))
Line 04) while (true) // loop forever
Line 05) ;
Line 06) else
Line 07) return; // FALSE or UNKNOWN
Line 08) }

Line 09) bool WillHalt01tring SourceCode, string InputData)
Line 10) {
Line 11) if (TheProgramWillHalt(SourceCode, InputData))
Line 12) return true;
Line 13) else
Line 14) return false;
Line 15) }

Line 16) void WillHalt02tring SourceCode, string InputData)
Line 17) {
Line 18) if (TheProgramWillHalt(SourceCode, InputData))
Line 19) SecureOutput("The Program Will Halt");
Line 20) else
Line 21) SecureOutput("The Program Will Not Halt");
Line 22) }

Line 23) WillHalt01(LoopIfHalts, LoopIfHalts)
Line 24) WillHalt02(LoopIfHalts, LoopIfHalts)
Line 25) WillHalt02(WillHalt01, LoopIfHalts)

The result of executing Line 23 is that bool WillHalt() returns false.
false indicates that the program will not halt. Since it does halt
false is the wrong answer.

Line 24 can not be executed (or produces a syntax error message)
because LoopIfHalts is attempting to check the return value of
a function that does not return a value.

Line 25 executes and outputs "The Program Will Halt" through
whatever secure channel is selected (such as the screen).

Relevant Pages