A New Kind of Science: The NKS Forum > Pure NKS > bidimensional tape turing machine
Author
victor g
omicron it
Paraguay

Registered: Jun 2006
Posts: 3

bidimensional tape turing machine

how can be defined the configuration of a bidimensional tape tm?

a unidimensional single tape has this configuration <q, x^i y>

where q is the state, x is the string before the pointer, ^ is the pointer, i is pointed, y is the string after i.

__________________
p = np, i got the proof but i lost it

Report this post to a moderator | IP: Logged

07-02-2006 02:44 AM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

If you simply mean a 2-D TM, the standard way is by having an array of values to represent the tape, and then changing the head location entry to a list rather than an integer, typically of the form {headstate, tape value}. This makes a nice data structure and is easy enough to work with, since a test for where an entry is a list rather than an integer returns the head position. E.g. -

{{0,0,0,0,0},
{0,0,1,0,0},
{0,0,{2,1},0,0},
{0,1,1,0,0},
{0,0,0,0,0}

That corresponds to a 5 by 5 region of tape with 1s at positions {2,3}, {3,3}, {4,2} and {4,3}, 0 elsewhere, and the head over position {3,3} in state 2. I find this data structure the clearest and most intuitive for the programmer.

Another way is to separately track head position and state in a first field, with the tape array in the second field - {head, tape} == {{head state, head position}, {{tape value, tape value, tape value,...}, {tape value, tape value, ...}}.

Naturally you can generalize either approach to multiple dimensions. The embedded list approach readily generalizes to multihead TMs and to minimalist agents (ant models e.g.). The second, prepended head data approach can also handle those but in my opinion it becomes much more cumbersome from a programmer's point of view.

In its favor, in the simplest case of these systems typically the tape away from the head is completely static, making it a waste to wrap functions or pattern questions over most of the first sort of data structure. Without the embedded list, the tape array might also be a sparse array data object, easier on memory requirements. So it may sometimes be more efficient in pure processing terms to use the prepended head data approach.

Report this post to a moderator | IP: Logged

07-13-2006 03:05 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us