Re: HALTING DISPROOF

• Previous message: Eray Ozkural exa: "Re: Panu Raatikainen's review of two of Chaitin's books."
• In reply to: The Ghost In The Machine: "Re: HALTING DISPROOF"
• Next in thread: The Ghost In The Machine: "Re: HALTING DISPROOF"
• Reply: The Ghost In The Machine: "Re: HALTING DISPROOF"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Sun, 16 May 2004 23:25:24 GMT

"The Ghost In The Machine" <ewill@aurigae.athghost7038suus.net> wrote
> Assume a simple infinite set of all TMs. Alternatively assume a simple UTM that
> > covers all TMs represented as naturals.
> >
> > Then, all computing power is represented by the set N.
> > The problem (and this is just a problem for you not me) is that some of the
> > TMs don't halt.
> >
> > Now assume infinite processing on the entire set of TMs, what do you have?
> >
> > You have a subset of N that are all demonstrably halting functions. This set I have always
> > thought is as powerful in computation as all N. Now everyone is arguing non-halting functions
> > add some power to functions but we can forget that for now that's just a copout.
> >
> > Now, to disprove a function halt exists, you have to be able to call functions and embed
> > them within other functions. This is not a paradigm of TMs.
> >
> > HALTING PROOF
> > 1 Assume a TM1 exists that inputs Naturals n and p, and outputs 1 iff UTM(n, p) halts.
> > 2 Assume another TM2 calls TM1(n, n) and goes into an infinite loop iff UTM(n, n) halts.
> > If TM2(n) halts, UTM(n, n) didn't halt.
>
> TM2 cannot call TM1, but can be constructed from the states in TM1.
> I know how you hate to label states, but in this case it might be
> useful.
>
> Assume TM1 exists, with starting state Btm1,
> set of states Stm1, transition function Ftm1, set of
> accepting states Atm1, and set of rejecting states Rtm1.
> (The modification is convenient because TM1 always halts,
> but a classical Turing machine doesn't distinguish between
> "halt and accept" and "halt and reject". If you want I
> can read the last symbol output from the tape instead,
> though that's more complicated. Admittedly, it is far
> from clear that TM1 can ever output 0, as non-halting
> Turing machines do not have an encoding in your system!)
>
> Now, do the following:
>
> [1] copy TM1 into TM2, lock, stock, and barrel, giving TM2 starting
> state Btm2, set of states Stm2, transition function Ftm2,
> accepting states Atm2, rejecting states Rtm2.
> [2] Add one additional state L.
> [3] Replace all transitions to a state in Atm2 with a transition
> to L.
> [4] Add transitions on all input symbols from L to L, no tape movement.
> (There's your loop.)
> [5] Throw out Atm2 (and its states), leaving only Rtm2 as a set of
> halting states for TM2.
>
> No calls here, just construction of another Turing machine given
> the states of the first one. Perfectly legitimate.
>
> If I've done this right TM2 should now be a potentially non-halting
> machine that takes two inputs n and p (the same as TM1), and loops
> if TM1 accepted, halts if TM1 rejected.
>
> Does TM2 have an encoding? If it does, that means it always
> halts. However, this encoding -- call it e2 -- can be fed
> into both TM1 and TM2. In the case of TM1 it will return 1 and
> end up in an accepting state in Atm1. In the case of TM2 it
> will end up in L, and the machine is now in a loop by design.
> Erm...
>
> Therefore TM2 has no encoding and TM1 can't exist to test
> encodings of machines that don't halt -- not because TM1
> is impossible but because your definition of "encoding"
> does not include machines that don't halt.

Restrictive godel numbers was not part of this demo, you can
assume any TM.

>
> If we assume that encoding includes machines that don't
> halt (the standard assumption), then we can complete the RIGHT!
> metaloop. Since TM2's encoding is the same (unless one wants
> to get really weird here), we can still feed it into both
> TM1 and TM2, running in parallel. TM1 always halts, and
> this time rejects -- indicating TM2 will not halt. TM2,
> unfortunately for TM1's definition, halts and announces
> "reject". Therefore TM1 gave the wrong answer.
>
> Since TM1 was designed to test *all* TM's, it's clear
> TM1 isn't doing its job and cannot exist.
>
> You can of course assume that TM1 doesn't halt or that TM1
> halts in a funny state but this means TM1 wasn't built properly.
>
> > If TM2(n) didn't halt, then UTM(n, n) halted.
> > Therefore UTM(n, n) can never equal TM2(n),
> > !En, UTM(n) = TM2,
> > the assumed function TM2 is therefore not compuable.
> >
> > So far so good, but WHY does this negate TM1?
>
> So construct TM1 already. I'll wait. :-) You should be
> able to without (much) difficulty, although my pathological
> TM2 will break it no matter how you construct TM1, as
> far as I can tell.
>
> > I won't detail it here I'll only get negative reponses,
> > I'll point out your flaw next reply.
>
> Go ahead. I think I've fixed it at this point.
>

Right! Adding a loop to the final states of the Halt TM is a standard
proof, you have to double up the parameter aswell. I'll stick to a
halting-tm-only godel numbers system. I thought if you could enumerate
programs one by one that halt and test them against the input you'd
make the halting function. I'll see if a subset of halting TMs is possible that
is still equivalent in power to any computing system. It would dissalow
a godel number for the infinite loop modification, and would argue in
theory such a TM is not a 'contributing' function.

Herc

• Previous message: Eray Ozkural exa: "Re: Panu Raatikainen's review of two of Chaitin's books."
• In reply to: The Ghost In The Machine: "Re: HALTING DISPROOF"
• Next in thread: The Ghost In The Machine: "Re: HALTING DISPROOF"
• Reply: The Ghost In The Machine: "Re: HALTING DISPROOF"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]