Re: resolving Will's misunderstanding

From: |-|erc (gotchy_at_beauty.com)
Date: 05/19/04 

Date: Wed, 19 May 2004 04:43:59 GMT

"Will Twentyman" <wtwentyman@read.my.sig> wrote
> > Making up a contradiction using G = lamba x (mod(F(x, x))) is NOT POSSIBLE
> > with a TM. It might be possible depending how easy F is to modify, but its
> > not always possible, F might be defined as mod2(G(x)), G is not free in F.
> > Do these situations arise with RAW TMs? Not at all.
>
> Let G be the states g1, g2, g3, g4, ... gm, UTM states, gm+1, gm+2, .., gh
> Let F be the states f1, f2, f3, f4, ... fn, UTM states, fn+1, fn+2, .., fk
>
> G has Godel number G1, F has Godel number F1.
>
> What if G lays down F1 on the tape followed by x, x, then enters the UTM
> states, then (rather than halting) performs lambda?
>
> What if F is similarly set up to lay G1 followed by x on the tape, enter
> the UTM, then perform mod2?
>
> This appears to do what you said is impossible.

F halts on all values. I'm assuming a UTM to substitute for F, so my theory
is a particular UTM exists that halts on all values. This was the original claim
remember?

The algorithm you described above, (setting down x x) has a trap built into it.
So given that UTM halts on all values, you have to ensure any modifications
to UTM also halt on all values. Making the data on the tape double is enough
to cause an infinite loop. This is what I demonstrated. My argument is weak
at this point that such a partial halting algorithm is not required computationally,
but without proof that it is I have demonstrated there is no flaw in the premise
that a set of complete halting functions can be enumerated.

>
> Seperate item. Thank you for being so tenacious. You are a wonderful
> prompt for me to brush up on the topic.

cool.

Herc

Relevant Pages