Mathematica 9 is now available
SEARCH MATHEMATICA 8 DOCUMENTATION
THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.
Mathematica > Mathematics and Algorithms > Computational Systems >
Mathematica > Mathematics and Algorithms > Discrete Mathematics > Computational Systems >
Built-in Mathematica SymbolSee Also »|More About »

TuringMachine

TuringMachine[rule, init, t]
generates a list representing the evolution of the Turing machine with the specified rule from initial condition init for t steps.
TuringMachine[rule, init]
gives the result of evolving init for one step.
  • For a 1D Turing machine, each step in the evolution generated by TuringMachine is given in the form {{s, x, dx}, {a1, a2, ...}}, where the head is in state s, the cells on the tape have values ai, the head is at position x relative to the ai, and has moved dx relative to its starting position.
  • If dx is omitted in the initial condition for a Turing machine, it is taken to be 0.
  • For a d-dimensional Turing machine, the tape is specified as a d-dimensional array, and the position x and relative position dx are length-d lists.
  • The rule for a Turing machine can be given as a list of replacements of the form {si, ai}->{spi, api, offi}, with elements as follows:
sistate of the head
aivalue of cell under the head
spinew state of the head
apinew value of cell under the head
offioffset by which the head moves
  • The states and cell values can be integers, patterns, or any other expressions. Individual cell values cannot be lists.
  • In one dimension, each offset offi is a single integer; in higher dimensions a list of integers.
  • When the states and cell values are taken to be integers in the range 1 to s and 0 to k-1 respectively, the following alternative forms can be given for rule:
n2-state, 2-color machine with number n
{n,s}s-state, 2-color machine with number n
{n,s,k}s-state, k-color machine with number n
{n,s,k,r}allow offi in the range -r to +r (excluding 0)
{n,s,k,{r1,r2,...,rd}}d-dimensional machine with +/-r_1, +/-r_2, ... offsets
{n,s,k,{{off1},{off2},...}}machine allowing the specified explicit offsets
rulemachine with explicit rule given
  • The number of possible Turing machine rules is as follows:
2-state 2-color machines4096
s-state k-color machines(2 s k)^(s k)
s-state k-color range r machines(2 r s k)^(s k)
2D s-state k-color machines(4 s k)^(s k)
  • If the machine has no rule for the configuration it is in, its configuration will not be changed.
  • Typical forms for the initial conditions init are as follows:
{s,{{},0}}head in state s, on a 1D tape filled with 0s
{s,{{a1,a2,...},0}}bounded region of values ai on an infinite tape
{{s,x},{{a1,a2,...},0}}bounded region with the head initially at position x
{{s,...},{{a1,...},{b1,...}}}repetitive background of value bi
{{s,...},{a1,a2,...}}finite tape, assumed cyclic
  • TuringMachine[rule, init, t] generates an evolution list of length t+1.
EXAMPLESCLOSE ALL
Basic Examples   (4)
2-state 2-color machine 2506 starting with a tape consisting of four 0s:
2-state 2-color machine 2506 with an infinite blank tape:
Plot the successive configurations of the tape:
"Inject" the state information into a representation of the tape:
Show the position of the head as a red square:
A machine given by a set of transition rules:
2-state 2-color machine 2506 starting with a tape consisting of four 0s:
In[1]:=
Click for copyable input
Out[1]=
 
2-state 2-color machine 2506 with an infinite blank tape:
In[1]:=
Click for copyable input
Out[1]=
Plot the successive configurations of the tape:
In[2]:=
Click for copyable input
Out[2]=
 
"Inject" the state information into a representation of the tape:
In[1]:=
Click for copyable input
Out[1]=
Show the position of the head as a red square:
In[2]:=
Click for copyable input
Out[2]=
 
A machine given by a set of transition rules:
In[1]:=
Click for copyable input
Out[1]=
Scope   (8)
3-state 2-color machine 2139050:
3-state 2-color machine 2139050, with jump offsets -1 and 2:
2-state 2-color machine 81756, with range 2:
Place the head at position 5 on the initial tape:
The tape can contain arbitrary expressions:
A 2D Turing machine:
A 2D Turing machine specified by explicit transitions:
Applications   (11)
Show the evolutions of a sequence of 2-state, 2-color machines:
Trajectory of machine head from successive initial conditions:
Path traced by a 2D machine:
Averaging tape of a 2D machine over many steps:
Successive states sequences from successive initial conditions:
Sequence of left or right movements for successive initial conditions:
Halting on a one-sided tape:
Computed function on a one-sided tape:
Show only steps on which the head reaches a new cell:
Show only steps on which the head returns to its initial location:
Causal network from random initial tape:
New in 6
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team