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

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 08/15/04 

Date: Sun, 15 Aug 2004 18:30:55 GMT

In sci.logic, Peter Olcott
<olcott@worldnet.att.net>
 wrote
on Sun, 15 Aug 2004 03:58:46 GMT
<WbBTc.209641$OB3.108770@bgtnsc05-news.ops.worldnet.att.net>:
>
> "The Ghost In The Machine" <ewill@aurigae.athghost7038suus.net>
> wrote in message news:ia12v1-q8o.ln1@lexi2.athghost7038suus.net...

[snip for brevity -- halting problem discussion]

>>
>> But that's exactly what Turing proved, by constructing
>> a LoopIfHalts given a machine implementing WillHalt that
>> can't be evaluated by (that particular variant of) WillHalt.
>
> Yet with my new whiz bang updated version of WillHalt, now
> LoopIfHalts and every other TM in the universal set of TMs
> can be correctly evaluated. www.halting-problem.com

Assuming that WillHalt can figure out that it's being
embedded (or one of its brothers is being embedded)
in the program under test -- and that your odd restriction
that there be no transitions out of the Halting state has
any meaning at all. It turns out LoopIfHalts can be implemented
as follows:

startstate: S
stateset: {S_i} union WillHalt(stateset) union {L,H}
haltset: {H}
transitionfunction:

     Handwaving here, sorry. The general idea is
     that LoopIfHalts will replace the second encoded
     parameter with an encoding based on its first and
     second encoding parameter -- the details depend on
     the encoding -- and then transition into the (mostly)
     embedded WillHalt's start state. The actual haltset
     (but not the states therein) of WillHalt has been
     discarded during the conversion of WillHalt to
     LoopIfHalts (this conversion is a 1-1 non-onto
     mapping of machine to machine), of course, but by
     the time LoopIfHalts gets to the old end state, the
     "0" or "1" has been written, and can be easily read.
     If "1", the machine transitions to loop in L. If "0",
     the machine transitions to halt in H.

WillHalt fails again.

I've already noted of course that there are many varieties of
WillHalt, assuming WillHalt exists at all; in the programming
language vernacular one can do such replacements as

MOV 0,Ri = XOR Ri, Ri or SUB Ri, Ri

and flip comparisons:

Jnz Ri,Label = Jz Ri,PC+2; JMP Ri,Label
CMP Ri, Rj; Jge Label = CMP Rj, Ri; Jle Label

Such "peephole" optimizations are well-known to compiler writers.

In the Turing machine realm, things aren't much
better. One can add idler states as one wishes (the TM
equivalent of "NOP"), by simply defining a transition
on any input without moving the head and splicing in the
new state. In a block-copy algorithm one might replace
a copy-by-one implementation using at least N states
(where N is the number of alphabetic symbols) with a
copy-by-two implementation using at least N(N+1) states.
There's probably other instances but I'm not all that up
on writing Turing machines. :-)

But even without these tricks, your analysis has a fatal flaw
anyway. WillHalt isn't even running in the emulator; it's
been transmogrified to something else (namely, LoopIfHalts).
WillHalt's final state is just another state in the transmogrified
machine. Is WillHalt smart enough to find itself? I doubt it!
To find itself it would have to *know* itself 100%, in some fashion,
and that's not all that possible-looking either, as anyone
who's tried to put the md5sum of an archive into the archive
knows.

As for "called from two different contexts" -- Turing
machines don't have contexts (merely state) and cannot be
called from one another, merely embedded. The programming
language equivalent is -Wl,-a,archive, which is an
occasionally-used link-time flag [*] to indicate that
every -l<name> reference should be dredged in from the .a
(archive) files, rather than the system doing the more
normal dynamic-load (.so).

[rest snipped]

[*] in Unix and Linux systems, anyway. There's an equivalent in Windows
    regarding .DLL and .LIB but I don't know what it is offhand. 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

Relevant Pages