Mathematica 9 is now available
THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.
Wolfram Mathematica Documentation Center
DOCUMENTATION CENTER SEARCH
New to Mathematica? Find your learning path »
Mathematica > Mathematics and Algorithms > Computational Systems > TuringMachine >
Mathematica > Mathematics and Algorithms > Discrete Mathematics > Computational Systems > TuringMachine >
BUILT-IN MATHEMATICA SYMBOLSee Also »|More About »

TuringMachine

TuringMachine
generates a list representing the evolution of the Turing machine with the specified rule from initial condition init for t steps.
TuringMachine
gives the result of evolving init for one step.
MORE INFORMATION
  • For a 1D Turing machine, each step in the evolution generated by TuringMachine is given in the form , where the head is in state s, the cells on the tape have values , the head is at position x relative to the , 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 .
  • 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 , 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 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:
n2-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 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
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
s-state k-color range r machines
2D s-state k-color machines
  • 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 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
{{s,...},{a1,a2,...}}finite tape, assumed cyclic
EXAMPLESCLOSE ALL
Basic Examples   (4)
2-state 2-color machine 2506 starting with a tape consisting of four 0s:
2-state 2-color machine 2506 with an infinite blank tape:
Plot the successive configurations of the tape:
"Inject" the state information into a representation of the tape:
Show the position of the head as a red square:
A machine given by a set of transition rules:
2-state 2-color machine 2506 starting with a tape consisting of four 0s:
In[1]:=
Click for copyable input
Out[1]=
 
2-state 2-color machine 2506 with an infinite blank tape:
In[1]:=
Click for copyable input
Out[1]=
Plot the successive configurations of the tape:
In[2]:=
Click for copyable input
Out[2]=
 
"Inject" the state information into a representation of the tape:
In[1]:=
Click for copyable input
Out[1]=
Show the position of the head as a red square:
In[2]:=
Click for copyable input
Out[2]=
 
A machine given by a set of transition rules:
In[1]:=
Click for copyable input
Out[1]=
Scope   (8)
3-state 2-color machine 2139050:
3-state 2-color machine 2139050, with jump offsets and :
2-state 2-color machine 81756, with range 2:
Place the head at position 5 on the initial tape:
The tape can contain arbitrary expressions:
A 2D Turing machine:
A 2D Turing machine specified by explicit transitions:
Applications   (11)
Show the evolutions of a sequence of 2-state, 2-color machines:
Trajectory of machine head from successive initial conditions:
Path traced by a 2D machine:
Averaging tape of a 2D machine over many steps:
Successive states sequences from successive initial conditions:
Sequence of left or right movements for successive initial conditions:
Halting on a one-sided tape:
Computed function on a one-sided tape:
Show only steps on which the head reaches a new cell:
Show only steps on which the head returns to its initial location:
Causal network from random initial tape:
New in 6
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team
Format:   HTML  |  CDF