Re: What is the Result from Invoking this Halt Function?

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

Date: Fri, 6 Aug 2004 14:31:15 +0000 (UTC)

Peter Olcott wrote:
> "Marc Goodman" <marc.goodman@comcast.net> wrote in message news:ibgQc.246159$Oq2.130858@attbi_s52...
>
>>Peter Olcott wrote:
>>
>>>All that Turing proved was that it is impossible to construct a Halt
>>>Analyzer that always returns the correct result of the Halt Analysis
>>>to the program (or TM) being analyzed.
>>
>>No. What he showed is that if a Halt determiner existed,
>>it could be used to construct a paradox.
>
>
> Yet this paradox that he constructed can only possibly exist under
> one specific circumstance and no others. If the halt analyzer simply
> refrains from ever providing its result to any program that is being
> analyzed, then this paradox becomes completely impossible to construct.
> That's exactly all that it takes, it takes nothing at all more than this.
> It really is just as simple as that.

If the halt analyzer is a Turing Machine, then it can't know who or what
invoked it. Therefore, it does not know whether or not to refrain from
returning its results. As a Turing Machine, it will *always* behave
*exactly* the same when given the same inputs. Therefore, if it fails
to return a result to a program which it's analyzing, it'll also fail to
return a result (for the same inputs) in all other circumstances. That
means that a Turing Machine can't be a halt analyzer.

> Before leaping into yet another round of incorrect refutation, try to first
> derive a single counter-example that correctly refutes the statement that
> I just made immediately above. Don't try to refute me without this
> counter-example, it would just waste more time, both mine and yours.

The error you keep making is that you rely on a Turing Machine being
able to tell whether or not it was invoked by the program being
analyzed. It can't. Therefore, we do not need to come up with *any*
counter-examples (though we have repeatedly pointed out the
counter-example provided by Alan Turing in 1936). It's already plain
and obvious from the definition of a Turing Machine that it cannot know
who or what invoked it, and that your reliance on it being able to tell
who or what invoked it means that you haven't refuted Turing's proof.

But, to spell it all out again, here's my thought experiment and
accompanying proof:-

Imagine that you are a halt analyzer, WillHalt. You are given a tape
with the following source code and input on it:-

Source code:

         bool LoopIfHalts(SourceCode s) {
           if (WillHalt(s, s)) {
             while(true); // Will loop forever.
             return true;
           else
             return false;
         }

Input:

         bool LoopIfHalts(SourceCode s) {
           if (WillHalt(s, s)) {
             while(true); // Will loop forever.
             return true;
           else
             return false;
         }

***IMPORTANT:***
However, as WillHalt, you do not know who or what gave you this tape. It
might have been LoopIfHalts; or it might have been someone or something
else.

As a halt analyzer, you have to determine whether or not
LoopIfHalts(LoopIfHalts) would halt, and you have to be able to return
your result. If LoopIfHalts(LoopIfHalts) would halt, return 'true';
otherwise, if it would not halt, return 'false'.

What result, if any, do you return?

A: 'true'.

B: 'false'.

C: No result is returned.

D: A result is returned, but it is neither 'true' nor 'false'.

Bear in mind that, as WillHalt, you do not know whether or not you were
invoked by LoopIfHalts. As a Turing Machine, you simply do not know who
or what gave you that tape.

And now for the proof of my refutation of your claims :-)

(1) WillHalt as a Turing Machine

No matter how many times you would be invoked, you would *never* know
who or what is invoking you. Therefore, whatever your answer is, it
would have to be the same for *all* invocations in which the tapes
you're given are identical to the one above. Otherwise, you would not
be behaving as a Turing Machine, as Turing Machines are incapable of
giving different results for the same inputs (as is obvious from the
definition of Turing Machines).

(2) WillHalt Can't Return 'true'

If your answer is A, 'true', then that would mean what you, as WillHalt,
would return 'true' *regardless* of who or what invoked you (because you
have no way of knowing who or what gave you the tape). That means you
would return 'true' when invoked by LoopIfHalts, and 'true' in all other
invocations. So, when LoopIfHalts(LoopIfHalts) invokes you, you would
return 'true', and LoopIfHalts would then never halt. When invoked as
just WillHalt(LoopIfHalts, LoopIfHalts), you would again return 'true',
but this would now be plainly incorrect. Therefore, if your answer is
A, you would be failing to match the definition of a halt analyzer.

(3) WillHalt Can't Return 'false'

If your answer is B, 'false', then that would mean what you, as
WillHalt, would return 'false' *regardless* of who or what invoked you
(because you have no way of knowing who or what gave you the tape). That
means you would return 'false' when invoked by LoopIfHalts, and 'false'
in all other invocations. So, when LoopIfHalts(LoopIfHalts) invokes
you, you would return 'false', and LoopIfHalts would then halt. When
invoked as just WillHalt(LoopIfHalts, LoopIfHalts), you would again
return 'false', but this would now be plainly incorrect. Therefore, if
your answer is B, you would be failing to match the definition of a halt
analyzer.

(4) WillHalt Must Return Something.

If your answer is C, then you would never return anything for that tape
*regardless* of who or what invoked you (because you have no way of
knowing who or what gave you the tape). Therefore, as you would never
return a result for tapes identical to the one above, you would be
failing to match the definition of a halt analyzer.

(5) WillHalt Must Return either 'true' or 'false'.

If your answer is D, then, whatever your result would be, you would
*always* return that *same* result for that tape *regardless* of who or
what invoked you (because you have no way of knowing who or what gave
you the tape). Therefore, as you would always return that result for
tapes identical to the one above, and as that result would be neither
'true' nor 'false', you would be failing to match the definition of a
halt analyzer.

(6) WillHalt Can't Be a Turing Machine and a Halt Analyzer

As now clearly proven, if WillHalt is a halt analyzer, and if WillHalt
is a Turing Machine (1), it cannot return either 'true' or 'false'
(2,3), but must return either 'true' or 'false' (4,5). This would
clearly be impossible, a plain contradiction. Therefore, it has been
proven that it is impossible for WillHalt to be both a halt analyzer and
a Turing Machine. This proof clearly applies to any replacement for
WillHalt. Therefore, your claim that it is possible for a Turing
Machine to be a halt analyzer is refuted.

(7) Turing Refuted Peter Olcott's Claim in 1936

As this proof here is the same as Turing's proof, it is also now proven
that Turing refuted your claim in 1936 :-)

Simon

Relevant Pages