({{, (RefLink[TuringMachine, paclet:ref/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. }, {, (RefLink[TuringMachine, paclet:ref/TuringMachine])[rule,init]
gives the result of evolving init for one step. }, {, (RefLink[TuringMachine, paclet:ref/TuringMachine])[rule]
is an operator form of (RefLink[TuringMachine, paclet:ref/TuringMachine]) that corresponds to one step of evolution.}})

OpenersNotesSection(Spacer1)Details

For a 1D Turing machine, each step in the evolution generated by (RefLink[TuringMachine, paclet:ref/TuringMachine]) is given in the form {{s,x,dx},{(Subscript[a, 1]),(Subscript[a, 2]),…}}, where the head is in state s, the cells on the tape have values (Subscript[a, i]), the head is at position x relative to the (Subscript[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 {(Subscript[s, i]),(Subscript[a, i])}->{(Subscript[sp, i]),(Subscript[ap, i]),(Subscript[off, i])}, with elements as follows:

The states and cell values can be integers, patterns, or any other expressions. Individual cell values cannot be lists.

In one dimension, each offset (Subscript[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:

The number of possible Turing machine rules is as follows:

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:

(RefLink[TuringMachine, paclet:ref/TuringMachine])[rule,init,t] generates an evolution list of length t+1.

(RefLink[TuringMachine, paclet:ref/TuringMachine])[rule][init] is equivalent to (RefLink[TuringMachine, paclet:ref/TuringMachine])[rule,init].

OpenersPrimaryExamplesSection(Spacer1)Examples  (36)

OpenersExampleSection0(Spacer1)Basic Examples  (4)

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

TuringMachine[2506,{1,{0,0,0,0}},3]

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

TuringMachine[2506,{1,{{},0}},4]

Plot the successive configurations of the tape:

ArrayPlot[Last/@TuringMachine[2506,{1,{{},0}},30]]

Show the rule icon for a Turing machine:

RulePlot[TuringMachine[2506]]

Plot the evolution, including the state of the head:

RulePlot[TuringMachine[2506],{1,{{},0}},20]

A Turing machine specified by explicit transitions:

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

OpenersExampleSection1(Spacer1)Scope  (16)

OpenersExampleSubsection0(Spacer1)One-Dimensional Rules  (5)

2-state, 2-color machine 2506:

TuringMachine[2506,{1,{{},0}},4]//Grid

Plot the evolution:

ArrayPlot[Last/@TuringMachine[2506,{1,{{},0}},20]]

Plot the evolution, including the state of the head:

RulePlot[TuringMachine[2506],{1,{{},0}},20]

3-state, 2-color machine 2139050:

RulePlot[TuringMachine[{2139050,3}],{1,{{},0}},30]

Generate a rule icon:

RulePlot[TuringMachine[{2139050,3}]]

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

ArrayPlot[Last/@TuringMachine[{16220,2,2,2},{1,{{},0}},50]]

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

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

ArrayPlot[Last/@evolution]

Give explicit transition rules:

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

evolution//Grid

OpenersExampleSubsection1(Spacer1)Initial Conditions  (9)

OpenersExampleSubsubsection0(Spacer1)Head Specification  (4)

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

TuringMachine[2506,{{1},{{},0}},4]//Grid

Evolution:

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

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

TuringMachine[2506,{{2},{{},0}},4]//Grid

Evolution:

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

Place the head at position 3 on the initial tape:

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:

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

OpenersExampleSubsubsection1(Spacer1)Tape Specification  (5)

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

TuringMachine[2506,{1,{0,0,0,0}},5]//Grid

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

RulePlot[TuringMachine[2506],{1,{0,0,0,0}},10]

Start with an infinite tape of 0s:

RulePlot[TuringMachine[2506],{1,{{},0}},18]

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

RulePlot[TuringMachine[{956440,3}],{1,{{1},0}},20]

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

RulePlot[TuringMachine[{596440,2,3}],{1,{{2,1,1},0}},10]

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

RulePlot[TuringMachine[{596440,2,3}],{1,{{2,1,1},{0,2}}},10]

OpenersExampleSubsection2(Spacer1)Multidimensional Rules  (2)

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

rule={977401,2,2,{1,1}};

TuringMachine[rule,{1,{{{}},0}},4]

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

Graphics3D[Cuboid/@Position[Last/@TuringMachine[rule,ic,steps],1]]

2D Turing machine specified by explicit transitions:

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}}};

ArrayPlot[TuringMachine[rules,{1,{{{}},0}},8000][[-1,-1]]]

OpenersExampleSection3(Spacer1)Applications  (12)

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

RulePlot[TuringMachine[{596440,2,3}],{1,{{},0}},80]

Alternative form using explicit rules:

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}};

RulePlot[TuringMachine[rules],{1,{{},0}},80]

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

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

Trajectory of the machine head from successive initial conditions:

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

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

Path traced by the head of a 2D machine:

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}}};

evolution=TuringMachine[rules,{1,{{{}},0}},200];

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

Graphics[{Arrowheads[.1],arrow,PointSize[Large],Gray,initpoint}]

Averaging tape of a 2D machine over many steps:

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

ArrayPlot[Total[Last/@TuringMachine[rules,ic,5000]]]

Successive states sequences from successive initial conditions:

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

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

Sequence of left or right movements for successive initial conditions:

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

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

Halting on a one-sided tape:

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

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:

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:

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:

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

Causal network from random initial tape:

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]]]]

OpenersExampleSection4(Spacer1)Properties & Relations  (4)

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:

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

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:

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

TuringMachine[rule,{inithstate,initcvalues},5]//Grid

Another Turing machine whose evolution halts:

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:

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

RulePlot[TuringMachine[rules]]

Plot the evolution:

RulePlot[TuringMachine[rules],{1,{{1,0},0}},8]

Generate a Turing machine evolution:

TuringMachine[2506,{1,{{},0}},6]

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

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:

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

Use (RefLink[RulePlot, paclet:ref/RulePlot]) to generate a complete evolution picture:

RulePlot[TuringMachine[2506],{1,{{},0}},50]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[CellularAutomaton, paclet:ref/CellularAutomaton])  ▪  (RefLink[RulePlot, paclet:ref/RulePlot])  ▪  (RefLink[SubstitutionSystem, paclet:ref/SubstitutionSystem])  ▪  (RefLink[BooleanFunction, paclet:ref/BooleanFunction])  ▪  (RefLink[AnglePath, paclet:ref/AnglePath])  ▪  (RefLink[AnglePath3D, paclet:ref/AnglePath3D])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Computational Systems, paclet:guide/ComputationalSystemsAndDiscovery])}, {▪(RefLinkPlain[Discrete Mathematics, paclet:guide/DiscreteMathematics])}, {▪(RefLinkPlain[Boolean Computation, paclet:guide/BooleanComputation])}, {▪(RefLinkPlain[Scientific Models, paclet:guide/ScientificModels])}})}})

({{(Spacer1), ({{(Spacer1)Related Links}, {(WebLink[DocumentationFooterIconsRelatedLinks-NKS.png(Spacer1)NKS|Online (, http://www.wolframscience.com/nksonline/section-3.4])(WebLink[A New Kind of Science), http://www.wolframscience.com/nksonline/section-3.4])}})}})