generates a list representing the evolution of the Turing machine with the specified rule from initial condition init for t steps.


gives the result of evolving init for one step.


is an operator form of TuringMachine that corresponds to one step of evolution.


  • 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:
  • n2state, 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 offi in the range -r to +r (excluding 0)
    {n,s,k,{r1,r2,,rd}}ddimensional 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(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 t+1.
  • TuringMachine[rule][init] is equivalent to TuringMachine[rule,init].


open all close all

Basic Examples  (4)

2-state, 2-color machine 2506 with an initial tape of four 0s, evolving for 3 steps:

Click for copyable input

2-state, 2-color machine 2506 with an infinite tape of 0s, evolving for 4 steps:

Click for copyable input

Plot the successive configurations of the tape:

Click for copyable input

Show the rule icon for a Turing machine:

Click for copyable input

Plot the evolution, including the state of the head:

Click for copyable input

A Turing machine specified by explicit transitions:

Click for copyable input

Scope  (16)

Applications  (12)

Properties & Relations  (4)

Introduced in 2007