SOLUTIONS

BUILTIN MATHEMATICA SYMBOL
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.
DetailsDetails
 For a 1D Turing machine, each step in the evolution generated by TuringMachine is given in the form , where the head is in state s, the cells on the tape have values , the head is at position x relative to the , 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 .
 For a ddimensional Turing machine, the tape is specified as a ddimensional array, and the position x and relative position dx are lengthd lists.
 The rule for a Turing machine can be given as a list of replacements of the form , with elements as follows:

s_{i} state of the head a_{i} value of cell under the head sp_{i} new state of the head ap_{i} new value of cell under the head off_{i} offset 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 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 and 0 to respectively, the following alternative forms can be given for rule:

n 2state, 2color machine with number n {n,s} sstate, 2color machine with number n {n,s,k} sstate, kcolor machine with number n {n,s,k,r} allow in the range to (excluding 0) {n,s,k,{r_{1},r_{2},...,r_{d}}} dimensional machine with , , ... offsets {n,s,k,{{off_{1}},{off_{2}},...}} machine allowing the specified explicit offsets rule machine with explicit rule given  The number of possible Turing machine rules is as follows:

2state 2color machines 4096 sstate kcolor machines sstate kcolor ranger machines 2D sstate kcolor machines  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,{{a_{1},a_{2},...},0}} bounded region of values on an infinite tape {{s,x},{{a_{1},a_{2},...},0}} bounded region with the head initially at position x {{s,...},{{a_{1},...},{b_{1},...}}} repetitive background of value {{s,...},{a_{1},a_{2},...}} finite tape, assumed cyclic  TuringMachine[rule, init, t] generates an evolution list of length .
ExamplesExamplesopen allclose all
Basic Examples (4)Basic Examples (4)
2state 2color machine 2506 starting with a tape consisting of four 0s:
In[1]:= 
Out[1]= 
2state 2color machine 2506 with an infinite blank tape:
In[1]:= 
Out[1]= 
Plot the successive configurations of the tape:
In[2]:= 
Out[2]= 
"Inject" the state information into a representation of the tape:
In[1]:= 
Out[1]= 
Show the position of the head as a red square:
In[2]:= 
Out[2]= 
A machine given by a set of transition rules:
In[1]:= 
Out[1]= 
New in 6
Mathematica 9 is now available!
New to Mathematica?
Find your learning path »
Have a question?
Ask support »