Re: Yet another Attempt at Disproving the Halting Problem

From: George Greene (greeneg_at_greeneg-cs.cs.unc.edu)
Date: 08/01/04 

Date: 01 Aug 2004 14:44:04 -0400

"Peter Olcott" <olcott@worldnet.att.net> writes:
 : //
 : // The following is computable
 : //

HTF would YOU know THAT? That is what we have been arguing about
the whole time! If WillHalt is in fact supposed to correctly
predict whether the program halts on the input, then it is NOT
computable. What we are talking about is a HYPOTHETICAL scenario
where we PRESUME that WillHalt is computable.

 : void LoopIfHalts(string ProgramSourceCode, string InputData)
 : {
 : if (WillHalt(ProgramSourceCode, InputData))
 : while (true)
 : ;
 : else
 : return;
 : }

Fine; that's a valid function declaration in your language.

 : bool WillHalt(LoopIfHalts, LoopIfHalts)

This, on the other hand, ISN'T.
It is ALSO not a valid function CALL.
If it were going to be an actual INVOCATION of WillHalt,
you would have to DROP the initial "bool" and replace
it with something like
if(WillHalt(LoopIfHalts, LoopIfHalts) { whatever }.
If, on the other hand, you were getting ready to actually
declare and define WillHalt here, then you would need SOME CODE, i.e.,
 bool WillHalt(LoopIfHalts, LoopIfHalts) { here is how we compute WillHalt. }

 : // Since WillHalt can see this source code, and its own source code

How do you know THAT? We don't know anything about WillHalt.

 : // It will know that it can not return true to LoopIfHalts, because
 : // LoopIfHalts would then go into an infinite loop, making this
 : // answer incorrect.

What WillHalt can see depends on how long and complicated WillHalt is.
More to the point, just because WillHalt can READ a piece of code does
NOT mean WillHalt can RUN that piece of code. If it can in fact run it,
then it may not be able to see in advance, BEFORE it starts running it,
that running it will get into an infinite loop.

 : // Therefore LoopIfHalts merely refrains from
 : // returning any value. This causes LoopIfHalts to immediately halt.

Only if WillHalt actually does what you say it does.
What if it CAN'T?

 : // None of this scenario is not computable.

WillHalt is not computable. 

-- 
 --- The history of our nation has demonstrated that separate is seldom, if ever, equal.
 --- (Feb.3,2004) Supreme Judicial Court of Massachusetts (4-3), adv.Sen.#2175

Relevant Pages