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

From: Owen Jacobson (angstrom_at_lionsanctuary.net)
Date: 08/04/04 

Date: Wed, 04 Aug 2004 03:11:56 GMT

On Wed, 04 Aug 2004 01:19:28 +0000, Peter Olcott wrote:

> "Karl Heinz Buchegger" <kbuchegg@gascad.at> wrote:
>
>> Peter Olcott 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);
>> >
>> > It has access to all of the source code, thus it can clearly see that
>> > the invocation of line 16 is different than the invocation of line 10.
>>
>> How come?
>> WillHalt has access to LoopIfHalts (and of course it's own Source Code)
>> only. LoopIfHalts is passed directly as Source Code to WillHalt and
>> WillHalt has to lookup the Source Code of WillHalt, since it is used
>> inside LoopIfHalts. But that's all. Line 16 is definitly out of Scope
>> for WillHalt.
>
> Since WillHalt has all of its own source code, it will already know that
> line 16 is not being used to change the result of the program that it is
> analyzing.

Line 16 in your example is neither part of the source of WillHalt nor the
source of LoopIfHalts. WillHalt therefore knows nothing about it. 

-- 
Some say the Wired doesn't have political borders like the real world,
but there are far too many nonsense-spouting anarchists or idiots who
think that pranks are a revolution.

Relevant Pages
Loading