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.
TuringMachine[rule]
is an operator form of TuringMachine that corresponds to one step of evolution.
Details



- 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:
-
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 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
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 offi 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 (2 s k)^(s k) s-state, k-color, range-r machines (2 r s k)^(s k) 2D s-state, k-color machines (8 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
.
- TuringMachine[rule][init] is equivalent to TuringMachine[rule,init].
Examples
open allclose allBasic Examples (4)
Scope (16)
Applications (12)
Properties & Relations (4)
See Also
CellularAutomaton RulePlot SubstitutionSystem BooleanFunction AnglePath AnglePath3D
Related Guides
Related Links
Introduced in 2007
(6.0)