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

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

Date: Sun, 22 Aug 2004 22:49:44 +0000 (UTC)

Marc Goodman wrote:
>
> Peter is talking about a TM that is extended to have access
> to its own state transition table. Imagine, for example, a
> TM with that extension that was calculating the MD5 checksum
> of its own state transition table. Any "local transformation"
> would be enough to change the result in such a case.
>
> So I don't believe that with the extension Peter is talking about,
> it's necessarily true that TransmogrifiedWillHalt and
> plain old WillHalt necessarily return the same values.
>
> Though I believe your proof below is reasonable for "plain old"
> TMs.

However, Olcott's augmented 'TM', P, is supposed to be run as a program
on a special 'UTM', V, that /is/ an ordinary TM. We can therefore
construct an ordinary TM that's equivalent to P-running-on-V, and then
transmogrify :-)

If Olcott's special 'UTM' isn't an ordinary TM, and if there can't be a
computationally equivalent TM, then so what? That would leave the
classic proof that no /TM/ could ever be a halt analyzer standing untouched.

At some point, it's got to come down to a TM that either is a halt
analyzer itself, or which runs a halt analyzer as a program. Either
way, it's not really difficult to constuct a classic halt-analyzing TM.
  The classic proof of its nonexistence then applies for that
constructed TM, and, by implication, also proves the nonexistence of
Olcott's TM and/or program.

Simon

Relevant Pages