[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


More information about the FOM mailing list