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

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

Date: Sat, 7 Aug 2004 12:14:52 +0000 (UTC)

Peter Olcott wrote:
> "David C. Ullrich" <ullrich@math.okstate.edu> wrote in message news:f7v6h0dmtd1strl0ftldjh6njr8oonvuns@4ax.com...
>
>>it's amazing how you seem unable to follow the simple proof that this
>>is not possible, regardless of how many times it's explained. one
>>more time:
>>
>>suppose that P is a program that does what you say - a correct halt
>>analyzer that refrains from returning the result under some
>>circumstances. now let Q be a program that does exactly what P
>>does, except that Q always does return 1 or 0. the proof shows
>>that Q cannot exist. hence P cannot exist. qed.
>
> Slight little error here that makes all the difference.
> You say that the conclusion that Q can't exist entails that P can't exist.
> Yet it is not that Q can't exist. Merely that Q sometimes reports results
> that are not correct.

Q always returns what P would return when P is invoked under those
circumstances in which P would return a result. Therefore, if Q
"sometimes reports results that are not correct", then it must be that P
"sometimes reports results that are not correct", and therefore P is not
a halt analyzer.

> This is a perfect example of a (otherwise) very well formed refutation,
> that just happens to be incorrect. I think that this is the basic form of
> all of the official and published refutations.
>
> This is either the key most crucial point that I am missing, or the key
> crucial point that everyone else (except me) has missed for sixty eight
> years.

The most crucial point that you are deliberately missing is that a
Turing Machine doesn't know who or what gave it its input tape. What
David Ullrich is doing is pointing out that even if we overlook this
fact, we can still prove that P cannot exist.

If it comes down to it, we can have Q invoke P, and lie to P by
pretending that it's something else that's invoking P. Turing Machines
only 'know' what we tell them, and we can lie to them (very easily,
because they only have themselves and their tapes to go on, and we have
complete control over what's on the tapes).

> Let's take this ALL THE WAY. Please explain to me exactly and precisely
> how is it that Q can not exist?

That's already been done. See my thought experiment and accompanying
proof. As Q, unlike P, /always/ returns its result /under all
circumstances/, my thought experiment and proof apply to Q.

> The way that I see it can perfectly well
> exist, yet sometimes provide incorrect results. I see nothing at all about
> Q that would in any possible way, by any stretch of the imagination
> prevent it from existing.

Then you are conceding that Turing's proof is correct.

Simon

Relevant Pages

  • Re: What is the Result from Invoking this Halt Function?
    ... Merely that Q sometimes reports results ... Turing Machine doesn't know who or what gave it its input tape. ... If it comes down to it, we can have Q invoke P, and lie to P by ... complete control over what's on the tapes). ...
    (sci.logic)
  • Re: Iraq update
    ... So you claim that being mistaken is the same as a lie? ... >> because crime happens quite often in real life. ... Yep, I would have given it the same weight, especially if the reports came ... >> You still haven't answered the question, is mistake the same as a lie? ...
    (rec.games.frp.dnd)
  • Re: Safety procedures generally used when removing mercury amalgams
    ... >That's a lie but don't expect the ADA to report it, ... Actually the ADA has ... >recieved 1000's of adverse reports about amalgam. ...
    (sci.med.dentistry)
  • Re: Iraq update
    ... I had to rely on the reports of people who were there. ... discussing the lies those people told and whether they should be free to lie ... > because crime happens quite often in real life. ... > You still haven't answered the question, is mistake the same as a lie? ...
    (rec.games.frp.dnd)
  • Re: Postcard from Atikokan
    ... of reports says the sky appears blue to the naked eye, ... Since the sky is not _actually_ blue, ... lie will be believed if it is repeated often enough". ... It's one thing to move the goalposts. ...
    (uk.local.cumbria)