Wolfram Language & System Documentation Center

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

Details and Options Details and Options

Examples

Basic Examples

Scope

One-Dimensional Rules

Initial Conditions

Head Specification

Tape Specification

Multidimensional Rules

Applications

Properties & Relations

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},{a₁,a₂,…}}, where the head is in state s, the cells on the tape have values a_i, the head is at position x relative to the a_i, 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 {s_i,a_i}->{sp_i,ap_i,off_i}, 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 off_i 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:
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 off_i in the range -r to +r (excluding 0)

{n,s,k,{r₁,r₂,…,r_d}} d‐dimensional machine with +/-r_(1), +/-r_(2), … offsets

{n,s,k,{{off₁},{off₂},…}} machine allowing the specified explicit offsets

{rule,s,k} machine with explicit rule given

rule machine with explicit rule given (and s, k inferred)
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.
If a rule has multiple specifications for a given configuration, TuringMachine will use the first one listed.
The form {rule,s,k} can be used to specify multiway, non-deterministic and other Turing machines in which there is not necessarily exactly one case in the rule for a given configuration.
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₁,a₂,…},0}} bounded region of values a_i on an infinite tape

{{s,x},{{a₁,a₂,…},0}} bounded region with the head initially at position x

{{s,…},{{a₁,…},{b₁,…}}} repetitive background of value b_i

{{s,…},{a₁,a₂,…}} 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].

Examples

open all close all

Basic Examples (5)

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

Wolfram Language code: TuringMachine[2506, {1, {0, 0, 0, 0}}, 3]

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

Wolfram Language code: TuringMachine[2506, {1, {{}, 0}}, 4]

Plot the successive configurations of the tape:

Wolfram Language code: ArrayPlot[Last /@ TuringMachine[2506, {1, {{}, 0}}, 30]]

Show the rule icon for a Turing machine:

Wolfram Language code: RulePlot[TuringMachine[2506]]

Plot the evolution, including the state of the head:

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {{}, 0}}, 20]

Show the rule icon for a Turing machine specified by explicit transitions:

Wolfram Language code: RulePlot[TuringMachine[{{1, 1} -> {2, 0, -1}, {1, 0} -> {2, 1, 1}, {2, 1} -> {1, 0, 1}, {2, 0} -> {1, 1, -1}}]]

Plot the evolution, including the state of the head:

Wolfram Language code:

RulePlot[TuringMachine[{{1, 1} -> {2, 0, -1}, {1, 0} -> {2, 1, 1}, {2, 1} -> {1, 0, 1}, {2, 0} -> {1, 1, -1}}], {1, {{}, 0}}, 20]

A Turing machine specified by pattern-based transition rules:

Wolfram Language code:

TuringMachine[{
	{state_, color_ ? EvenQ} :> {state, color / 2, -1}, {state_, color_ ? OddQ} :> {state, 3color + 1, 1}}, 
	{1, {1, 2, 3, 4, 5}}, 5]

Scope (17)

One-Dimensional Rules (6)

2-state, 2-color machine 2506:

Wolfram Language code: TuringMachine[2506, {1, {{}, 0}}, 4]//Grid

Plot the evolution:

Wolfram Language code: ArrayPlot[Last /@ TuringMachine[2506, {1, {{}, 0}}, 20]]

Plot the evolution, including the state of the head:

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {{}, 0}}, 20]

3-state, 2-color machine 2139050:

Wolfram Language code: RulePlot[TuringMachine[{2139050, 3}], {1, {{}, 0}}, 30]

Generate a rule icon:

Wolfram Language code: RulePlot[TuringMachine[{2139050, 3}]]

2-state, 2-color machine 16220, with range 2:

Wolfram Language code: ArrayPlot[Last /@ TuringMachine[{16220, 2, 2, 2}, {1, {{}, 0}}, 50]]

3-state, 2-color machine 2139050, with jump offsets and 2:

Wolfram Language code: evolution = TuringMachine[{2139050, 3, 2, {{-1}, {2}}}, {1, {{}, 0}}, 45];

Wolfram Language code: ArrayPlot[Last /@ evolution]

Give explicit transition rules:

Wolfram Language code:

evolution = TuringMachine[
	{{state_, color_} :> {color * state, color / state, 1}}, 
	{1, {2, 3, 4, 5}}, 4];

Wolfram Language code: evolution//Grid

Explicitly specify values of the number of states s and the number of colors k for the same transition rules:

Wolfram Language code: rules = {{1, 1} -> {2, 0, -1}, {1, 0} -> {2, 1, 1}, {2, 1} -> {1, 0, 1}, {2, 0} -> {1, 1, -1}};

Wolfram Language code: RulePlot[TuringMachine[{rules, 2, 2}]]

Wolfram Language code: RulePlot[TuringMachine[{rules, 3, 3}]]

Initial Conditions (9)

Head Specification (4)

2-state, 2-color machine 2506 with head initially in state 1:

Wolfram Language code: TuringMachine[2506, {{1}, {{}, 0}}, 4]//Grid

Evolution:

Wolfram Language code: RulePlot[TuringMachine[2506], {{1}, {{}, 0}}, 20, PlotLegends -> "Icon"]

2-state, 2-color machine 2506 with head initially in state 2:

Wolfram Language code: TuringMachine[2506, {{2}, {{}, 0}}, 4]//Grid

Evolution:

Wolfram Language code: RulePlot[TuringMachine[2506], {{2}, {{}, 0}}, 10, PlotLegends -> "Icon"]

Place the head at position 3 on the initial tape:

Wolfram Language code: RulePlot[TuringMachine[2506], {{1, 3}, {0, 0, 0, 0, 1, 0, 0}}, 10, PlotLegends -> "Icon"]

Place the head at position 5 on the initial tape:

Wolfram Language code: RulePlot[TuringMachine[2506], {{1, 5}, {0, 0, 0, 0, 1, 0, 0}}, 10, PlotLegends -> "Icon"]

Tape Specification (5)

Start with a finite tape of four 0s, assumed cyclic:

Wolfram Language code: TuringMachine[2506, {1, {0, 0, 0, 0}}, 5]//Grid

The left neighbor of the leftmost cell is the rightmost cell, and vice versa:

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {0, 0, 0, 0}}, 10]

Start with an infinite tape of 0s:

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {{}, 0}}, 18]

Start with a tape of 1 on an infinite background of 0s:

Wolfram Language code: RulePlot[TuringMachine[{956440, 3}], {1, {{1}, 0}}, 20]

Start with a tape consisting of the block 211 on a background of 0s:

Wolfram Language code: RulePlot[TuringMachine[{596440, 2, 3}], {1, {{2, 1, 1}, 0}}, 10]

Start with the block 211 on a background of repeated 02 blocks:

Wolfram Language code: RulePlot[TuringMachine[{596440, 2, 3}], {1, {{2, 1, 1}, {0, 2}}}, 10]

Multidimensional Rules (2)

2D 2-state, 2-color Turing machine 977401:

Wolfram Language code: rule = {977401, 2, 2, {1, 1}};

Wolfram Language code: TuringMachine[rule, {1, {{{}}, 0}}, 4]

Wolfram Language code:

ic = {1, Table[0, {10}, {10}]};
steps = 30;

Wolfram Language code: Graphics3D[Cuboid /@ Position[Last /@ TuringMachine[rule, ic, steps], 1]]

2D Turing machine specified by explicit transitions:

Wolfram Language code:

rules = {
	{1, 0} -> {2, 1, {0, 1}}, {1, 1} -> {2, 0, {0, -1}}, 
	{2, 0} -> {4, 1, {0, -1}}, {2, 1} -> {3, 0, {0, 1}}, 
	{3, 0} -> {1, 1, {-1, 0}}, {3, 1} -> {2, 1, {0, 1}}, 
	{4, 0} -> {3, 1, {0, -1}}, {4, 1} -> {2, 0, {1, 0}}};

Wolfram Language code: ArrayPlot[TuringMachine[rules, {1, {{{}}, 0}}, 8000][[-1, -1]]]

Applications (12)

Evolution of Wolfram's simplest universal Turing machine from an infinite tape of 0s:

Wolfram Language code: RulePlot[TuringMachine[{596440, 2, 3}], {1, {{}, 0}}, 80]

Alternative form using explicit rules:

Wolfram Language code:

rules = {{1, 2} -> {1, 1, -1}, {1, 1} -> {1, 2, -1}, {1, 0} -> {2, 1, 1}, {2, 2} -> {1, 0, 1}, {2, 1} -> {2, 2, 1}, {2, 0} -> {1, 2, -1}};

Wolfram Language code: RulePlot[TuringMachine[rules], {1, {{}, 0}}, 80]

Show the evolutions of a sequence of 2-state, 2-color machines:

Wolfram Language code: Table[RulePlot[TuringMachine[n], {1, {{}, 0}}, 40, ImageSize -> {Automatic, 100}], {n, 2500, 2510}]

Trajectory of the machine head from successive initial conditions:

Wolfram Language code: ic[n_] := {{1, -2, 0}, {IntegerDigits[n, 2, 20], 0}};

Wolfram Language code: ListLinePlot[Table[#[[1, 3]]& /@ TuringMachine[1507, ic[i], 180], {i, 1, 40}]]

Path traced by the head of a 2D machine:

Wolfram Language code:

rules = {
	{1, 0} -> {2, 1, {0, 1}}, {1, 1} -> {2, 0, {0, -1}}, 
	{2, 0} -> {4, 1, {0, -1}}, {2, 1} -> {3, 0, {0, 1}}, 
	{3, 0} -> {1, 1, {-1, 0}}, {3, 1} -> {2, 1, {0, 1}}, 
	{4, 0} -> {3, 1, {0, -1}}, {4, 1} -> {2, 0, {1, 0}}};

Wolfram Language code: evolution = TuringMachine[rules, {1, {{{}}, 0}}, 200];

Wolfram Language code:

arrow = Arrow[#[[1, 3]]& /@ evolution];
initpoint = Point[First[evolution][[1, 3]]];

Wolfram Language code: Graphics[{Arrowheads[.1], arrow, PointSize[Large], Gray, initpoint}]

Averaging tape of a 2D machine over many steps:

Wolfram Language code:

rules = {27726, 2, 2, {1, 1}};
ic = {1, Table[0, {50}, {50}]};

Wolfram Language code: ArrayPlot[Total[Last /@ TuringMachine[rules, ic, 5000]]]

Successive states sequences from successive initial conditions:

Wolfram Language code: ic[n_] := {1, {IntegerDigits[n, 2, 20], 0}};

Wolfram Language code: ArrayPlot[Table[#[[1, 1]]& /@ TuringMachine[1507, ic[i], 100], {i, 1, 100}] - 1]

Sequence of left or right movements for successive initial conditions:

Wolfram Language code: ic[n_] := {1, {IntegerDigits[n, 2, 20], 0}};

Wolfram Language code: ArrayPlot[Table[Differences[#[[1, 3]]& /@ TuringMachine[1507, ic[i], 100]], {i, 1, 100}] /. -1 -> 0]

Halting on a one-sided tape:

Wolfram Language code:

TuringPlot[evolution_, opts___] := ArrayPlot[MapAt[Blend[{If[# === Orange, #, GrayLevel[#]], Red}]&, #[[2]], #[[1, 2]]]& /@ (evolution /. Null -> Orange), opts]

Wolfram Language code:

Row[Table[TuringPlot[TuringMachine[1507, {{1, -2, 0}, Append[IntegerDigits[i, 2, 10], Null]}, 15], Mesh -> True, ImageSize -> Tiny], {i, 10}], Spacer[10]]

Computed function on a one-sided tape:

Wolfram Language code:

ListPlot[Table[Last@TuringMachine[1507, {{1, -2, 0}, Append[IntegerDigits[i, 2, 20], Null]}, 50] /. {{{_, z_, _}, y_} /; y[[z]] === Null :> FromDigits[Most[y], 2], _ -> Null}, {i, 1, 1000}], Filling -> Axis]

Show only steps on which the head reaches a new cell:

Wolfram Language code:

Module[{new}, new[x_] := (new[x] = False;True);
	RulePlot[TuringMachine[{2791284850, 4}], 
	Cases[
	TuringMachine[{2791284850, 4}, {1, {{}, 0}}, 200], {{_, _, _ ? new}, _}], 
	Mesh -> True]
	]

Show only steps on which the head returns to its initial location:

Wolfram Language code: RulePlot[TuringMachine[1413], Select[TuringMachine[1413, {1, RandomInteger[1, 100]}, 6000], #[[1, 2]] === 1&]]

Causal network from random initial tape:

Wolfram Language code:

GraphPlot[With[{rules = MapIndexed[{First[#2], #[[1, 2]], #[[2, #[[1, 2]]]]}&, TuringMachine[1507, {1, RandomInteger[1, 30]}, 200]]}, Join[Rule@@@Partition[rules, 2, 1], Flatten[Rule@@@Partition[#, 2, 1]& /@ Last@Reap[Sow[#, #[[2]]]& /@ rules], 1]]]]

Properties & Relations (5)

2-state, 2-color machine 2506 with an initial tape of four 0s, evolving for a single step:

Wolfram Language code: TuringMachine[2506, {1, {0, 0, 0, 0}}]

Equivalently, use the operator form on the initial condition:

Wolfram Language code: TuringMachine[2506][{1, {0, 0, 0, 0}}]

The result corresponds to the second element in this list:

Wolfram Language code: TuringMachine[2506, {1, {0, 0, 0, 0}}, 1]

For rules of the form {n,s,k,…}, head states and cell values can be integers in the range 1 to s and 0 to k-1, respectively:

Wolfram Language code:

rule = {596440, 2, 4};
inithstate = 2;
initcvalues = {{}, {2, 1, 3}};

Wolfram Language code: TuringMachine[rule, {inithstate, initcvalues}, 5]//Grid

For rules of the form {n,s,k,…}, if the head reaches a cell whose value is not in the range 0 to k-1, the evolution of the machine halts:

Wolfram Language code:

rule = {596440, 2, 4};
inithstate = 2;
initcvalues = {{}, {2, 1, 8}};

Wolfram Language code: TuringMachine[rule, {inithstate, initcvalues}, 5]//Grid

Another Turing machine whose evolution halts:

Wolfram Language code: ArrayPlot[Last /@ TuringMachine[2506, {1, {{0, 0, 0, 0, 0, x, 0}, 0}}, 40]]

Use an explicit set of rules to define a halting state:

Wolfram Language code:

rules = {
	{1, 0} -> {1, 1, 1}, {1, 1} -> {2, 1, -1}, 
	{2, 0} -> {1, 1, 1}, {2, 1} -> {2, 1, 0}};

Wolfram Language code: RulePlot[TuringMachine[rules]]

Plot the evolution:

Wolfram Language code: RulePlot[TuringMachine[rules], {1, {{1, 0}, 0}}, 8]

Generate a Turing machine evolution:

Wolfram Language code: TuringMachine[2506, {1, {{}, 0}}, 6]

"Inject" the state information into a representation of the tape:

Wolfram Language code: Function[u, MapAt[{u[[1, 1]], #}&, u[[2]], u[[1, 2]]]] /@ TuringMachine[2506, {1, {{}, 0}}, 6]

Show the position of the head as a red square:

Wolfram Language code: ArrayPlot[Function[u, MapAt[Red&, u[[2]], u[[1, 2]]]] /@ TuringMachine[2506, {1, {{}, 0}}, 50]]

Use RulePlot to generate a complete evolution picture:

Wolfram Language code: RulePlot[TuringMachine[2506], {1, {{}, 0}}, 50]

Related Guides

▪

Computational Systems

▪

Discrete Mathematics

▪

Boolean Computation

▪

Scientific Models

History

Introduced in 2007 (6.0) | Updated in 2021 (12.3)

Wolfram Research (2007), TuringMachine, Wolfram Language function, https://reference.wolfram.com/language/ref/TuringMachine.html (updated 2021).

Text

Wolfram Research (2007), TuringMachine, Wolfram Language function, https://reference.wolfram.com/language/ref/TuringMachine.html (updated 2021).

CMS

Wolfram Language. 2007. "TuringMachine." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2021. https://reference.wolfram.com/language/ref/TuringMachine.html.

APA

Wolfram Language. (2007). TuringMachine. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/TuringMachine.html

BibTeX

@misc{reference.wolfram_2026_turingmachine, author="Wolfram Research", title="{TuringMachine}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/TuringMachine.html}", note=[Accessed: 11-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_turingmachine, organization={Wolfram Research}, title={TuringMachine}, year={2021}, url={https://reference.wolfram.com/language/ref/TuringMachine.html}, note=[Accessed: 11-June-2026]}

Top [フレーム]

More Learning

Tech Support

Wolfram Solutions

Wolfram Solutions For Education

Get Started

Grow Your Skills

Work with Us

Educational Programs for Adults

Educational Programs for Youth

Read

TuringMachine

Details

Examples

Basic Examples (5)

Scope (17)

One-Dimensional Rules (6)

Initial Conditions (9)

Head Specification (4)

Tape Specification (5)

Multidimensional Rules (2)

Applications (12)

Properties & Relations (5)

See Also

Related Guides

Related Links

History

Text

CMS

APA

BibTeX

BibLaTeX