[bidimensional tape turing machine] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


bidimensional tape turing machine

(Click here to view the original thread with full colors/images)


Posted by: victor g

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.


Posted by: Jason Cawley

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.




Forum Sponsored by Wolfram Research

© 2004-2013 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings