A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > bidimensional tape turing machine
  Last Thread   Next Thread
Thread Post New Thread    Post A Reply
victor g
omicron it

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

Old Post 07-02-2006 02:44 AM
victor g is offline Click Here to See the Profile for victor g Click here to Send victor g a Private Message Click Here to Email victor g Visit victor g's homepage! Edit/Delete Message Reply w/Quote
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. -


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

Old Post 07-13-2006 03:05 PM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


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

Forum Sponsored by Wolfram Research

© 2004-16 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives