BUILT-IN WOLFRAM LANGUAGE 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.
- 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 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
, with elements as follows:
-
| si | state of the head |
| ai | value of cell under the head |
| spi | new state of the head |
| api | new value of cell under the head |
| offi | 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 | 2‐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  in the range  to  (excluding 0) |
| {n,s,k,{r1,r2,…,rd}} |  ‐dimensional machine with  ,  , … offsets |
| {n,s,k,{{off1},{off2},…}} | machine allowing the specified explicit offsets |
| rule | machine with explicit rule given |
- The number of possible Turing machine rules is as follows:
-
| 2-state 2-color machines | 4096 |
| s-state k-color machines |  |
| s-state k-color range-r machines |  |
| 2D s-state k-color 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,{{a1,a2,…},0}} | bounded region of values  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  |
| {{s,…},{a1,a2,…}} | finite tape, assumed cyclic |
- TuringMachine[rule,init,t] generates an evolution list of length
.
2-state 2-color machine 2506 starting with a tape consisting of four 0s:
| Out[1]= |  |
2-state 2-color machine 2506 with an infinite blank tape:
| Out[1]= |  |
Plot the successive configurations of the tape:
| Out[2]= |  |
"Inject" the state information into a representation of the tape:
| Out[1]= |  |
Show the position of the head as a red square:
| Out[2]= |  |
A machine given by a set of transition rules:
| Out[1]= |  |
