[FOM] 2,3 Turing machine proof controversy

Alex Galicki alex.galicki at googlemail.com
Fri Nov 9 23:42:16 EST 2007


On 10/11/2007, Vaughan Pratt <pratt at cs.stanford.edu> wrote:

> > Imagine the following input:
> >
> > ...__R0110_01X_R0110_01XX_110XX_R0110_01XXX_110XXX_01XXX_R...
> >
> > This input tells the system to emulate the cyclic tag system for one
> > step, then two steps, then three steps, then so on. The input to this
> > system isn't periodic, but is simple to construct in a non-universal
> > way. Is this Turing machine universal?
>
> Let's say it's at least less objectionable than a machine that has to be
> repeatedly restarted "manually" (deus ex machina).
>
> > With the definition I used in
> > the 2,3 Turing machine universality proof, yes.
>
> No, because this machine manages its own restarts without outside
> intervention, whereas the definition in your proof allowed manual
> restarting.

Could you, please, be more specific? What do you mean by 'manual restarting'?

By the way: could you tell me what is the halting rule of the 2,3
machine? I know its strange to ask you these questions, but it seems
that your understanding of how that machine works is much better then
mine.

A.


More information about the FOM mailing list