WOLFRAM

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.

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:
  • 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
    {rule,s,k}machine with explicit rule given
    rulemachine with explicit rule given (and s, k inferred)
  • 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.
  • 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,{{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].

Examples

open allclose all

Basic Examples  (5)Summary of the most common use cases

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

Out[1]=1

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

Out[1]=1

Plot the successive configurations of the tape:

Out[2]=2

Show the rule icon for a Turing machine:

Out[1]=1

Plot the evolution, including the state of the head:

Out[2]=2

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

Out[1]=1

Plot the evolution, including the state of the head:

Out[2]=2

A Turing machine specified by pattern-based transition rules:

Out[1]=1

Scope  (17)Survey of the scope of standard use cases

One-Dimensional Rules  (6)

2-state, 2-color machine 2506:

Out[1]=1

Plot the evolution:

Out[2]=2

Plot the evolution, including the state of the head:

Out[3]=3

3-state, 2-color machine 2139050:

Out[1]=1

Generate a rule icon:

Out[2]=2

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

Out[1]=1

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

Out[2]=2

Give explicit transition rules:

Out[2]=2

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

Out[2]=2
Out[3]=3

Initial Conditions  (9)

Head Specification  (4)

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

Out[1]=1

Evolution:

Out[2]=2

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

Out[1]=1

Evolution:

Out[2]=2

Place the head at position 3 on the initial tape:

Out[1]=1

Place the head at position 5 on the initial tape:

Out[1]=1

Tape Specification  (5)

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

Out[1]=1

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

Out[2]=2

Start with an infinite tape of 0s:

Out[1]=1

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

Out[1]=1

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

Out[1]=1

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

Out[1]=1

Multidimensional Rules  (2)

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

Out[2]=2
Out[5]=5

2D Turing machine specified by explicit transitions:

Out[2]=2

Applications  (12)Sample problems that can be solved with this function

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

Out[1]=1

Alternative form using explicit rules:

Out[3]=3

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

Out[1]=1

Trajectory of the machine head from successive initial conditions:

Out[2]=2

Path traced by the head of a 2D machine:

Out[4]=4

Averaging tape of a 2D machine over many steps:

Out[2]=2

Successive states sequences from successive initial conditions:

Out[2]=2

Sequence of left or right movements for successive initial conditions:

Out[2]=2

Halting on a one-sided tape:

Out[2]=2

Computed function on a one-sided tape:

Out[1]=1

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

Out[1]=1

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

Out[1]=1

Causal network from random initial tape:

Out[1]=1

Properties & Relations  (4)Properties of the function, and connections to other functions

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:

Out[4]=4

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:

Out[2]=2

Another Turing machine whose evolution halts:

Out[3]=3

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

Out[2]=2

Plot the evolution:

Out[3]=3

Generate a Turing machine evolution:

Out[1]=1

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

Out[2]=2

Show the position of the head as a red square:

Out[3]=3

Use RulePlot to generate a complete evolution picture:

Out[4]=4
Wolfram Research (2007), TuringMachine, Wolfram Language function, https://reference.wolfram.com/language/ref/TuringMachine.html (updated 2021).
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).

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.

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

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

BibTeX

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

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

BibLaTeX

@online{reference.wolfram_2024_turingmachine, organization={Wolfram Research}, title={TuringMachine}, year={2021}, url={https://reference.wolfram.com/language/ref/TuringMachine.html}, note=[Accessed: 10-January-2025 ]}

@online{reference.wolfram_2024_turingmachine, organization={Wolfram Research}, title={TuringMachine}, year={2021}, url={https://reference.wolfram.com/language/ref/TuringMachine.html}, note=[Accessed: 10-January-2025 ]}