Re: Smaller UTM than Rule110

From: Tim Tyler (tim_at_tt1lock.org)
Date: 01/04/05 

Date: Tue, 4 Jan 2005 20:49:39 GMT

Rick Decker <rdecker@hamilton.edu> wrote or quoted:
> Tim Tyler wrote:
> > I, Tim Tyler <tim@tt1lock.org> wrote or quoted:

> >>Since one of the main points of a Turing machine is that it
> >>is an abstract model of serial computation, such unnecessary
> >>and superfluous features seem rather undesirable.
> >
> > Another problem I see with Turing machines as an abstract model
> > of serial computation is that they are *defined* as only having
> > "back" and "forward" states.
> >
> > What's with that?
> >
> > It causes most two-dimensional serial digital machines to fail to
> > qualify as a Turing machines :-(
>
> No it doesn't. The inclusion of a two-dimensional "tape" along
> with forward/back/up/down moves of the head gives you a machine
> that is equivalent to a vanilla TM. Many intro theory texts
> contain proofs of this.

AFAICS, machines with Up/Down/Left/Right operations fail to qualify as
Turing machines - according to most popular definitions.

In particular, they fail according to definitions on the previously-cited
pages:

  http://plato.stanford.edu/entries/turing-machine/

...and...

  http://en.wikipedia.org/wiki/Turing_machine

Of course a 2D machine can do all the same computations a one
dimensional machine can do - but being "Turing equivalent" is
not the same as being a "Turing machine". 

-- 
__________
 |im |yler  http://timtyler.org/  tim@tt1lock.org  Remove lock to reply.

Relevant Pages

  • Re: Smaller UTM than Rule110
    ... machines with Up/Down/Left/Right operations fail to qualify as ... Turing machines - according to most popular definitions. ... dimensional machine can do - but being "Turing equivalent" is ...
    (comp.theory)
  • Re: Smaller UTM than Rule110
    ... >> variations in the number of head states and number ... >> of movement directions are not? ... why does the term "Turing equivalent" exist? ... as Turing machines get classified as *being* "Turing machines" - ...
    (comp.theory)
  • Re: Smaller UTM than Rule110
    ... >> variations in the number of head states and number ... >> of movement directions are not? ... why does the term "Turing equivalent" exist? ... as Turing machines get classified as *being* "Turing machines" - ...
    (sci.logic)
  • Re: Smaller UTM than Rule110
    ... Many intro theory texts ... > Turing machines - according to most popular definitions. ... Look at section 3: Varieties of Turing Machines. ... I take it you would disallow multi-tape TMs, ...
    (sci.logic)
  • Re: Smaller UTM than Rule110
    ... Many intro theory texts ... > Turing machines - according to most popular definitions. ... Look at section 3: Varieties of Turing Machines. ... I take it you would disallow multi-tape TMs, ...
    (comp.theory)