Re: The proof that I was referring to is on the website

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

Date: Thu, 5 Aug 2004 12:48:51 +0000 (UTC)

This post contains a /really good/ thought experiment for you to do.
It's the best way I can think of to try to demonstrate to you what the
ongoing flaw in your reasoning is.

Peter Olcott wrote:
> "Simon G Best" <s.g.best@btopenworld.com> wrote in message news:4110F32C.7000503@btopenworld.com...
>>
>>Your attempted refutation relies on a halt analyzer sometimes behaving
>>differently under /different/ conditions but with the /same/ inputs.
>>That means it can't be a Turing Machine. Same inputs, same behaviour -
>>*always*.
>
> No the input differs

In Turing's proof, the inputs do not differ. This is obvious in
Turing's proof. The tapes given to the halt analyzer are *identical* in
both cases.

> Line 01) void LoopIfHalts(string SourceCode)

(Good to see you've got a correct declaration now :-) )

> Line 02) {
> Line 03) if (WillHalt(SourceCode, SourceCode) == TRUE)
> Line 04) while (TRUE) // loop forever
> Line 05) ;
> Line 06) else
> Line 07) return; // FALSE or UNKNOWN
> Line 08) }
>
> Line 09) cout << WillHalt(LoopIfHalts, LoopIfHalts);
>
> A smart halt analyzer would be able to see that the combination
> of lines 03 and 04, result in special case processing. WillHalt()
> can safely (and correctly) assume that the invocation of line 09
> does not involve any special processing.
>
> (1) It has all of its own source code available to it. (line 03)
>
> (2) Any special situations are only possible within the sourcecode
> that is provided to it, (it can't be reasonable expected to correctly
> analyze any behavior where source code is not provided.)
> thus line 09 is not a special case.

You're still mixing up the invocation it's analyzing, and the running
invocation within which it's doing that analysis. That's where you keep
going wrong.

Imagine that you're WillHalt, and you're given a tape with (LoopIfHalts,
LoopIfHalts) on it (and that's all that's on it). You don't know who or
what gave you that tape, because the tape itself is the only input you
have. What result, if any, do you, as WillHalt return? (Bear in mind
that it might, or might not, have been LoopIfHalts that gave you that tape.)

Possible answers (return results):-

A: true

B: false

Simon

Relevant Pages