Re: Solution to the halting Problem?

From: Stewart Gordon (smjg_1998_at_yahoo.com)
Date: 07/23/04 

Date: Fri, 23 Jul 2004 10:56:54 +0100

Peter Olcott wrote:
>>> Since it is possible to write X that does not return a value to
>>> its caller, then its possible to prevent the basis for proving
>>> that solving the Halting Problem is impossible to exist.
>>
>> That doesn't follow. If it's possible to write a function that
>> calculates X, how can it be impossible to modify it so that it
>> returns X? Can you supply an example of such a function?
>
> The function that does not return a value does correctly determine
> halting for all inputs, including the function that does return this
> value.

Then so will the one generated by modifying your algorithm, replacing
all occurrences of 'write the result to console' or whatever with
'return the result', and changing nothing else.

Even if the result is built up and written to the console little by
little, all occurrences of 'write to console' can be replaced by 'write
to a file', and then the final action of WillHalt can be to read the
file back in and return its contents. Or you can bypass the file, and
use an in-memory buffer.

<snip>
>> No I haven't. Disproving the validity of a proof is very different
>> from disproving the original theorem. The people who found fault
>> in the many
>
> A single valid counter-example is all that is required. I provided
> that.
<snip>

What are you referring to as "a single valid counter-example"? A single
algorithm that can be proven to halt or not halt given arbitrary input?
  That isn't what the halting problem means.

Or a single version of WillHalt that will not work with the original
proof? A necessary prerequisite for the theorem to be false is that
your version of WillHalt genuinely cannot be changed into one that is
compatible with the proof. And obviously your example doesn't satisfy
this requirement.

The logic of the proof is still there, it just has one more link in its
chain.

WillHalt can be constructed
   => WillHalt that returns its result can be constructed
   => The LoopIfHalts function can be constructed based on the
result-returning WillHalt
   => The LoopIfHaltsOnItself function can be constructed
   => LoopIfHaltsOnItself can be applied to itself
   => Contradiction.

Here, I'll go down in history for having just extended the standard
proof to deal with your idea.

Stewart. 

-- 
My e-mail is valid but not my primary mailbox, aside from its being the 
unfortunate victim of intensive mail-bombing at the moment.  Please keep 
replies on the 'group where everyone may benefit.

Relevant Pages