The Turing Machine
The Turing Machine
One of Alan Turing’s many fundamental contributions to the foundations of computer science was his 1937 formulation of the Turing machine. A Turing machine is a general-purpose theoretical computer that provides a way to formalize and analyze computation. It consists of: 1) a line of cells known as a "tape" that can be moved back and forth; 2) an active element known as the "head" that possesses a property known as "state", and that can change the property known as "color" of the active cell underneath it; and 3) a set of instructions for modifying the active cell and subsequently moving the tape. At each step, the machine may modify the color of the active cell and change the state of the head. After this, it moves the tape one unit to the left or right.
Turing performed his foundational investigations of Turing machines using hand computation. With the benefit of modern electronic computers, a number of fascinating results concerning Turing machines have been investigated and established.
Exploring Turing machines is particularly straightforward in the Wolfram Language using the built-in TuringMachine function. To evaluate the examples below, simply click an input, hold and press the key.
A Simple Example
A Simple Example
First, consider a 2-state, 2-color Turing machine. Since there are two states and two colors, the number of possible rules (state/color transitions) needed to specify the machine's behavior is . Allow the state s of the head to be either 1 (visualized as the head pointing up) or 2 (head pointing down), and the color c under it to be 1 (indicated in yellow) or 2 (indicated in white). Further, denote a post-update tape movement to the left by -1, and a movement to the right by +1. The following set of four rules then defines a particular Turing machine (number 1222 in the Wolfram Language enumeration), whose action can be visualized as follows:
24
2
In[1]:=
RulePlot[TuringMachine[rules={
{1,1}{1,1,-1},
{1,0}{1,1,1},
{2,1}{1,0,-1},
{2,0}{2,1,-1}
}]]
Out[1]=
Interpret the rules as {s, c} {s', c', Δ} , where s and s' are the original and changed states, c and c' are the original and changed colors and Δ is the direction in which the tape is moved. The first rule {1, 1} {1, 1, -1} says, "If the head is up and the color under it is yellow, keep the head up, mark the cell under it yellow and move the tape one step to the left." Similarly, the second rule says, "If the head is up and the color under it is white, keep the head up, mark the cell under it yellow and move the tape one step to the right."
We can now run this Turing machine with initial conditions {1, {{}, 0}}—meaning the head is in state 1 operating on a tape filled with all 0s—for some fixed number of steps, say 5:
In[2]:=
TuringMachine[rules,{1,{{},0}},5]//Column
Out[2]=
{{1,1,0},{0,0,0,0,0,0}} |
{{1,2,1},{1,0,0,0,0,0}} |
{{1,3,2},{1,1,0,0,0,0}} |
{{1,4,3},{1,1,1,0,0,0}} |
{{1,5,4},{1,1,1,1,0,0}} |
{{1,6,5},{1,1,1,1,1,0}} |
The result is a list of evolution steps of the form {{s, x, dx}, , where for each step, s indicates the state of the head, x is the head position, dx is the offset of the head from its initial position and gives the values written to the tape.
{a,a}}
1
2,…
{a,a}
1
2,…
The evolution can be easily visualized:
In[3]:=
RulePlot[TuringMachine[rules],{1,{{},0}},10,MeshTrue]