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

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

Date: Wed, 04 Aug 2004 02:15:00 GMT

"Simon G Best" <s.g.best@btopenworld.com> wrote in message news:410F33D0.1040608@btopenworld.com...
> Peter Olcott wrote:
> [...]
> >
> > I have thought about this quite extensively over the past few days.
> > I have come to the conclusion that it is correct to say that an identical
> > method with identical input must produce identical results.
>
> Well done! :-D
>
> [...]
>
> > In this case we have identical methods. It is not even an identical copy of
> > the same method. It is the very same method.
>
> Correct.
>
> > What we do not have is identical data.
>
> Incorrect. The data is identical in both cases. In Turing's proof, the
> data is identical in both cases.

I am running out of time for today.
I will post a breif point here:
it is something like this.

WillHalt(LoopIfHalts, LoopIfHalts)
WillHalt(WillHalt(LoopIfHalts, LoopIfHalts))

> If H was to have different data in the two cases, it would no longer be
> the situation Turing used, and would no longer refute Turing's proof.
> Turing's proof relies on the situation which Turing used where the data
> is identical in both cases.
>
> You've also got the following 'C++' code wrong:-
>
> > 01) int WillHalt(string SourceCode, string DataInput)
>
> You're declaring WillHalt to be a function of type 'int (string,
> string)'. (It takes /strings/ for arguments.)
>
> > 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)
>
> You're declaring LoopIfHalts to be a function that takes /two/ arguments.
>
> > 09) {
> > 10) if (WillHalt(SourceCode, DataInput))
> > 11) while(true)
> > 12) ;
> > 13) else
> > 14) return;
> > 15) }
> >
> > 16) cout << WillHalt(LoopIfHalts, LoopIfHalts);
>
> But WillHalt treats its first argument as representing a function taking
> /one/ argument.
>
> What's more, LoopIfHalts is a /function/, but WillHalt takes /strings/
> for arguments.
>
> > Because of Line 16, WillHalt has all of its own source code (or TM description)
> > available to it. It would be unreasonable to ask a halt analyzer to determine if
> > a program (or TM) halts, and not provide it every bit of all of the source code
> > (or TM description).
> >
> > Because it can see all of its own source-code, it can see that the invocation
> > on line 16 would not be fed back to another TM such that this TM can change
> > its behavior, and thus change the result of the halt analysis.
>
> No. This is plainly wrong. It *cannot* see line 16, because line 16 is
> not part of LoopIfHalts, and is not part of WillHalt, and is not part of
> TheProgramHalts, either.
>
> In both cases, WillHalt *only* gets the arguments (LoopIfHalts,
> LoopIfHalts). It gets no other information or data *at all*.
>
> (Even if WillHalt /could/ access some extra data, perhaps by examining
> the computer's call stack, /it has to ignore that data/. Otherwise, the
> situation in your 'C++' example fails to be equivalent to the situation
> which Turing used. WillHalt has to behave /as if its arguments are the
> only data available to it./)
>
> > Because it can also see all of the source code for LoopIfHalts, it knows
> > that its returned result IS used by the program being analyzed to change
> > its behavior, and thus change the result of the halt analysis. From this it can
> > see that a true return value would result in an incorrect answer. Since the
> > designers of the halt analyzer (me) thought it better to refrain from providing
> > an answer, rather than to provide an incorrect answer, these same designers
> > (me) deemed that it would refrain from providing a return value in these cases.
>
> If you, the "designers", 'designed' WillHalt that way, it fails to match
> the *definition* of a halt analyzer. The hypothetical halt analyzer in
> Turing's proof is *defined* to *always* return an answer, *no matter
> what*. As a result, the situation in your 'C++' example fails to refute
> Turing's proof.
>
> > So the halt analyzer knowing all this can see that line 16 can safely provide
> > the return value of 1, indicating that LoopIfHalts will halt.
>
> No, because WillHalt can't see line 16.
>
> > It knows this
> > because it also knows that it would refrain from providing an answer on
> > line 10. Because of this design enhancement, what was once thought to
> > be impossible, is actually quite easy. WillHalt is no longer prohibited
> > from correctly processing any programs.
>
> The last line is in contradiction with what you said about the 'design'
> of WillHalt. You've made it clear that WillHalt, as you've 'designed'
> it, *is* sometimes "prohibited from correctly processing" (LoopIfHalts,
> LoopIfHalts).
>
> I suggest you stop trying to do it in C++, as you keep making the same
> mistakes over and over again with it. It doesn't seem to matter how
> many times people point out these same mistakes, you keep making them.
>
> Now, you yourself have referred (in some other posts) to the
> Church-Turing Thesis. The Church-Turing Thesis means that you simply
> don't need to even try to do it in C++. Just stick with Turing
> Machines, as Turing defined them, and there'll be less confusion.
>
> Simon
>

Relevant Pages