TuringMachine
✖
TuringMachine
generates a list representing the evolution of the Turing machine with the specified rule from initial condition init for t steps.
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,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,{{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 (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:
https://wolfram.com/xid/05fhu82zw0-jlou4s
2-state, 2-color machine 2506 with an infinite tape of 0s, evolving for 4 steps:
https://wolfram.com/xid/05fhu82zw0-25sjdq
Plot the successive configurations of the tape:
https://wolfram.com/xid/05fhu82zw0-rdad8o
Show the rule icon for a Turing machine:
https://wolfram.com/xid/05fhu82zw0-m4o7v2
Plot the evolution, including the state of the head:
https://wolfram.com/xid/05fhu82zw0-gqnbwx
Show the rule icon for a Turing machine specified by explicit transitions:
https://wolfram.com/xid/05fhu82zw0-fdthtx
Plot the evolution, including the state of the head:
https://wolfram.com/xid/05fhu82zw0-703x0q
A Turing machine specified by pattern-based transition rules:
https://wolfram.com/xid/05fhu82zw0-kqht5
Scope (17)Survey of the scope of standard use cases
One-Dimensional Rules (6)
2-state, 2-color machine 2506:
https://wolfram.com/xid/05fhu82zw0-j453f8
https://wolfram.com/xid/05fhu82zw0-b38bvb
Plot the evolution, including the state of the head:
https://wolfram.com/xid/05fhu82zw0-c5ao3h
3-state, 2-color machine 2139050:
https://wolfram.com/xid/05fhu82zw0-gtqxg1
https://wolfram.com/xid/05fhu82zw0-eob5ep
2-state, 2-color machine 16220, with range 2:
https://wolfram.com/xid/05fhu82zw0-4r0y80
3-state, 2-color machine 2139050, with jump offsets and 2:
https://wolfram.com/xid/05fhu82zw0-dkqfai
https://wolfram.com/xid/05fhu82zw0-byvd75
Give explicit transition rules:
https://wolfram.com/xid/05fhu82zw0-hgbytw
https://wolfram.com/xid/05fhu82zw0-h79g4
Explicitly specify values of the number of states s and the number of colors k for the same transition rules:
https://wolfram.com/xid/05fhu82zw0-ulibwn
https://wolfram.com/xid/05fhu82zw0-sskr7s
https://wolfram.com/xid/05fhu82zw0-iqqziz
Initial Conditions (9)
Head Specification (4)
2-state, 2-color machine 2506 with head initially in state 1:
https://wolfram.com/xid/05fhu82zw0-grj8zj
https://wolfram.com/xid/05fhu82zw0-igt2r4
2-state, 2-color machine 2506 with head initially in state 2:
https://wolfram.com/xid/05fhu82zw0-kuyavj
https://wolfram.com/xid/05fhu82zw0-5z20h
Place the head at position 3 on the initial tape:
https://wolfram.com/xid/05fhu82zw0-edptul
Place the head at position 5 on the initial tape:
https://wolfram.com/xid/05fhu82zw0-h22olx
Tape Specification (5)
Start with a finite tape of four 0s, assumed cyclic:
https://wolfram.com/xid/05fhu82zw0-gat6go
The left neighbor of the leftmost cell is the rightmost cell, and vice versa:
https://wolfram.com/xid/05fhu82zw0-b492a3
Start with an infinite tape of 0s:
https://wolfram.com/xid/05fhu82zw0-i1r1fh
Start with a tape of 1 on an infinite background of 0s:
https://wolfram.com/xid/05fhu82zw0-jmhp6
Start with a tape consisting of the block 211 on a background of 0s:
https://wolfram.com/xid/05fhu82zw0-f85h3v
Start with the block 211 on a background of repeated 02 blocks:
https://wolfram.com/xid/05fhu82zw0-e6u3e0
Multidimensional Rules (2)
2D 2-state, 2-color Turing machine 977401:
https://wolfram.com/xid/05fhu82zw0-luxd0y
https://wolfram.com/xid/05fhu82zw0-f3mdxr
https://wolfram.com/xid/05fhu82zw0-d66lt7
https://wolfram.com/xid/05fhu82zw0-g6hb26
2D Turing machine specified by explicit transitions:
https://wolfram.com/xid/05fhu82zw0-bj5hii
https://wolfram.com/xid/05fhu82zw0-l298ne
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:
https://wolfram.com/xid/05fhu82zw0-6rsh
Alternative form using explicit rules:
https://wolfram.com/xid/05fhu82zw0-u3py4
https://wolfram.com/xid/05fhu82zw0-bj487w
Show the evolutions of a sequence of 2-state, 2-color machines:
https://wolfram.com/xid/05fhu82zw0-hl2otg
Trajectory of the machine head from successive initial conditions:
https://wolfram.com/xid/05fhu82zw0-ivsilz
https://wolfram.com/xid/05fhu82zw0-i06ykt
Path traced by the head of a 2D machine:
https://wolfram.com/xid/05fhu82zw0-yi23j
https://wolfram.com/xid/05fhu82zw0-bwots
https://wolfram.com/xid/05fhu82zw0-cg2jcn
https://wolfram.com/xid/05fhu82zw0-blz8hz
Averaging tape of a 2D machine over many steps:
https://wolfram.com/xid/05fhu82zw0-f49j6
https://wolfram.com/xid/05fhu82zw0-vqvfyh
Successive states sequences from successive initial conditions:
https://wolfram.com/xid/05fhu82zw0-k3ej55
https://wolfram.com/xid/05fhu82zw0-gb8dsc
Sequence of left or right movements for successive initial conditions:
https://wolfram.com/xid/05fhu82zw0-qy3ua
https://wolfram.com/xid/05fhu82zw0-pc52xs
https://wolfram.com/xid/05fhu82zw0-9noex5
https://wolfram.com/xid/05fhu82zw0-49d0x4
Computed function on a one-sided tape:
https://wolfram.com/xid/05fhu82zw0-zldtxc
Show only steps on which the head reaches a new cell:
https://wolfram.com/xid/05fhu82zw0-iowrq1
Show only steps on which the head returns to its initial location:
https://wolfram.com/xid/05fhu82zw0-8t87lp
Causal network from random initial tape:
https://wolfram.com/xid/05fhu82zw0-j4wgyn
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:
https://wolfram.com/xid/05fhu82zw0-betwt3
https://wolfram.com/xid/05fhu82zw0-ifptir
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:
https://wolfram.com/xid/05fhu82zw0-bp95xp
https://wolfram.com/xid/05fhu82zw0-7mxxk
Another Turing machine whose evolution halts:
https://wolfram.com/xid/05fhu82zw0-egiluu
Use an explicit set of rules to define a halting state:
https://wolfram.com/xid/05fhu82zw0-qltxu
https://wolfram.com/xid/05fhu82zw0-nn66ku
https://wolfram.com/xid/05fhu82zw0-bb8idi
Generate a Turing machine evolution:
https://wolfram.com/xid/05fhu82zw0-5irdm6
"Inject" the state information into a representation of the tape:
https://wolfram.com/xid/05fhu82zw0-49p2g
Show the position of the head as a red square:
https://wolfram.com/xid/05fhu82zw0-bllsan
Use RulePlot to generate a complete evolution picture:
https://wolfram.com/xid/05fhu82zw0-ca8ex6
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
]}
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
]}