[FOM] 2,3 Turing machine proof controversy
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
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