Re: Yet another Attempt at Disproving the Halting Problem

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

Date: Fri, 6 Aug 2004 13:37:21 +0000 (UTC)

Peter Olcott wrote:
>
> Alan Turing conclusively proved is that it is impossible to construct a
> halt analyzer that always returns a correct result back to the program
> being analyzed.

Yes, we all agree on that :-D

> Since returning the result back to the program being analyzed is not the
> only way to construct a halt analyzer, his proof did not show that constructing
> a halt analyzer that works correctly for all input is impossible.

As repeatedly explained, it does not know whether or not the program
being analyzed was the program that invoked it.

Therefore, if it doesn't return a result when invoked by that program,
it won't return a result when invoked by someone or something else. If
it does return a result when invoked by someone or something else, it
will return the same result when invoked by the program being analyzed.

Again, here is a thought experiment to prove that this is a correct
refutation of your ignorantly repeated claims:-

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 :-)

> The paradox that he constructed to show that a halt analyzer can
> not be constructed can only possibly exist under one specific circumstance
> and no others.

And that is enough to prove that a halt analyzer cannot be a Turing Machine.

> 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.

(1), (4) and (5) above are the proof that a Turing Machine can't be a
halt analyzer if it "simply refrains from ever providing its result to
any program that is being analyzed".

> That's exactly all that it takes, it takes
> nothing at all more than this. It really is just as simple as that.
>
> I will make a little prediction here. Given until the end of time no
> one will ever be able to correctly refute the above statements.

Too late. Alan Turing refuted your claim in 1936.

Simon

Relevant Pages

  • Re: Yet another Attempt at Disproving the Halting Problem
    ... > only way to construct a halt analyzer, his proof did not show that constructing ... However, as WillHalt, you do not know who or what gave you this tape. ... As a Turing Machine, you simply do not know who ... invokes you, you would return 'false', and LoopIfHalts would then halt. ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... > faintest idea what method Turing used. ... requires the halt analyzer to return its results to every caller. ... > you accept that diagonalisation is valid, and as you also accept that ... > What do you mean 'the pure math version'. ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... > faintest idea what method Turing used. ... requires the halt analyzer to return its results to every caller. ... > you accept that diagonalisation is valid, and as you also accept that ... > What do you mean 'the pure math version'. ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... responding to "Peter Olcott" ... In my opinion, you have difficulty distinguishing what you think Turing ... > a halt analyzer that works correctly for all input is impossible. ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... responding to "Peter Olcott" ... In my opinion, you have difficulty distinguishing what you think Turing ... > a halt analyzer that works correctly for all input is impossible. ...
    (comp.theory)