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

From: Simon G Best (s.g.best_at_btopenworld.com)
Date: 08/03/04 

Date: Tue, 3 Aug 2004 06:41:21 +0000 (UTC)

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.

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