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

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

Date: 06 Aug 2004 14:51:21 -0400

 : > <olcott@worldnet.att.net> wrote:
 :
 : > >Line 01) void LoopIfHalts(string SourceCode, string InputData)
 : > >Line 02) {
 : > >Line 03) if (WillHalt(SourceCode, InputData) == TRUE)
 : > >Line 04) while (TRUE) // loop forever
 : > >Line 05) ;
 : > >Line 06) else
 : > >Line 07) return; // FALSE or UNKNOWN
 : > >Line 08) }
 : > >
 : > >Are you in Denial or what? What does lines 03 and 04 do???

 : "David C. Ullrich" <ullrich@math.okstate.edu> wrote in message news:omi1h09lm1ducfchgeimbv71qbn3umh9hb@4ax.com...
 : > On Wed, 04 Aug 2004 02:09:06 GMT, "Peter Olcott"
 : > it goes into an infinite loop if willhalt says that the
 : > program being analyzed, namely 'SourceCode, InputData',
 : > halts.
 : >
 : > it certainly does not modify the behavior of that
 : > program. [hint: those two lines are part of loopifhalts,

PO:
 : Ah so then you are saying that the behavior of LoopIfHalts
 : would be identical when WillHalt returns true, as it would be
 : if WillHalt returned something other than true?

Of course not. You can see, right there, it HAS an if/else;
it does one thing if WillHalt returns true and a different
thing if it returns false.

 : The Boolean return value of true returned to LoopIfHalts
 : alters the behavior of LoopIfHalts as contrasted with the
 : behavior of LoopIfHalts when a Boolean value of true is
 : not returned to it.

Of course.

 : Basically telling LoopIfHalts that it will halt
                                      ^^

You CANNOT tell LoopIfHalts that *it* will halt.
You can ONLY tell LoopIfHalts that SourceCode will or
won't halt on InputData. That SourceCode happens
to BE LoopIfHalts (occasionally) IS IRRELEVANT and,
more to the point, IS IMPOSSIBLE for LoopIfHalts (itself)
TO EVEN KNOW! There are literally infinitely many different
programs out there that have the EXACT SAME HALTING BEHAVIOR
(over all possible InputDatas) AS LoopIfHalts, but are NOT
LoopIfHalts. And any EQUIVALENT program would produce the
same contradiction.

 : makes it NOT HALT, so simply don't tell it!

You CAN'T not tell it, not once you've called WillHalt!
WillHalt IS a Boolean function! If IT halts (and WillHalt
ALWAYS halts, on EVERY input, BY DEFINITION), then it MUST
return a boolean value. IT HAS NO CHOICE. BY DEFINITION.
More to the point, LoopIfHalts, itself, by virtue of saying
if(
in c++, is DEMANDING a boolean value. So there WILL be
a boolean value forthcoming here. DEAL WITH IT.

Here's a direct question to Peter that is long overdue:

How old are you?
Seriously, you don't sound old enough to have graduated from
college 20 years ago (I should know; I did). Are you just
using your Dad's email account? 

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