7.5. TURING MACHINES

This section under major construction.

Turing machine. The Turing machine is one of the most beautiful and intriguing intellectual discoveries of the 20th century. It is a simple and useful model of computation that is general enough to embody any computer program. It forms the foundation of theoretical computer science. Because of its simple description and behavior, it is amenable to mathematical analysis. This analysis has led to a deeper understanding of computers and computation, including the revelation that there are some computational problems that cannot be solved on computers at all, no matter how fast the processor, or how much memory is available.

Turing machine simulator. This is a graphical Turing Machine simulator that was written in Java by Tom Ventimiglia under the supervision of Bob Sedgewick and Kevin Wayne. You need Java Web Start to run the Turing machine simulator. Here's an executable JAR in case that's more convenient. You are welcome to inspect and modify the source code for your own use.

Components. Alan Turing sought to describe the most primitive model of a mechanical device that had the same basic capabilities as a human "computer." In his epoch making 1936 paper, Alan Turing introduced an abstract machine, which would later come to be known as a Turing machine. The machine consists of the following components:

The ticker-tape stores the input, the intermediate results, and the output. The tape is one arbitrarily long strip, divided into cells. Each cell stores one of a finite alphabet of symbols. In the example below, we use a 5 character alphabet consisting of 0, 1, A, B, and #.
The tape head of the Turing machine scans the tape one cell at a time. We refer to the cell being scanned as the active cell and the symbol it contains as the imput symbol. At each time step, the tape head reads the input symbol, and leaves it either unchanged or overwrites it with a new symbol. At the end of each time step, the tape head moves one position to the left or right. We highlight the active cell in yellow. In the example below, the A is replaced with an X and the tape head moves to the right.
The control unit is the analog of the CPU in modern day microprocessors. It consists of a state transition diagram, which is a finite table of instructions that specifies exactly what action the machine takes at each step. Each state represents one of the possible configurations of the machine. Depending on its current state and input symbol, the Turing machine overwrites the input symbol with a new symbol and moves to a new state. Each transition connects one state, say s, to another state, say t, and is labeled with two symbols, say A and X: this means that if the Turing machine is in state s and the input symbol is A, then it overwrite the A with an X and transitions to state t. Each state is labeled with one of five designations: L (left), R (right), Y (yes), N (no), or H (halt). Upon entering a state, the Turing machine either moves its tape head or halts according to the state's designation. Below is an illustration of the state transition diagram for a machine with five states.

Execution. Initially the Turing machine starts in one distinguished state called the start state, and the tape head points to one distinguished cell called the start cell. There is at most one possible transition corresponding to each combination of state and input symbol; thus, the actions of the machine are completely determined in advance. (If there is no possible transition from a state with some input symbol, then the Turing machine remains in the same state and does not overwrite the input symbol.) Each step in a Turing machine proceeds as follows:

Read the input symbol from the active cell.
Look up the transition rule associated with the current state and input symbol.
Overwrite the input symbol with the new symbol.
Change the current state according to the transition rule.
Shift the tape head one cell to the left or right, according to the new state's designation.

These steps are repeated until the current state is labeled H for halt, Y (in which case the machine answers yes) or N (in which case the machine answers no). It is possible that the machine runs forever without ever reaching one of these terminating states.

An example: unary to binary conversion. We consider the 5 state Turing machine illustrated below. The current state and input symbol are highlighted in yellow. We trace its execution until it halts.

Since the input symbol is A, the Turing machine follows the appropriate transition arrow leaving the current state - the one labeled A : X. The Turing machine overwrites the input symbol with an X, changes state to the bottom left state, and moves the tape head one position to the right (since the new state is labeled with R). The illustration below shows the Turing machine at the end of this first step.

Since the input symbol is now A, the Turing machine follows the appropriate transition arrow leaving the current state -- the one labeled A : A. This overwrites the current cell with an A (no change), changes the state back to the upper left state, and moves the tape head one position to the right (since the new state is labeled with R). This process of overwriting an A on the tape with an X and then skipping the next A repeats until all of the A's are examined. The contents of the tape after each of these 5 steps is shown below.

Since there were an even number of A's on the tape originally, the Turing machine is in the upper left state after the last A is examined. At this point the Turing machine follows the transition arrow labeled #:# as illustrated below.

Now, the input symbol is A. Since there is no transition arrow leaving the current state corresponding to this symbol, the Turing machine remains in the current state, moving the tape head to the left. This action is repeated until the tape head reaches the left end of the original input. The tape contents after the next 6 steps are illustrated below.

Oops, the second to the last non-blank column below should be all X's.

Now, the Turing machine overwrites the # with a 0, as illustrated below.

The tape contents after the next 15 steps are shown below. As before, the Turing machine scans from left to right, overwriting every other A with an X. since there were an odd number of A's (3) at the beginning of this phase, the Turing machine writes a 1 at the left end of the tape.

The tape contents after the next 17 steps are shown below. Again, the Turing machine scans from left to right, overwriting every other A with an X. since there were an odd number of A's (1) at the beginning of this phase, the Turing machine writes a 1 at the left end of the tape.

The tape contents after the final 8 steps are shown below. Since there are no more A's, the Turing machine enters the state labeled H and halts.

How it works. The Turing machine described above converts from unary to binary. That is, if the input consists of n consecutive A's, then the Turing machine prints the number n in binary to the left of sequence of A's (and overwrites the A's with X's). In the example above, the input consists of 6 A's and the Turing machine writes the binary number 110 to the tape.

To describe how this is accomplished, we first review an algorithm for converting an integer n to binary.

WHILE (n > 0) {
   IF (n % 2 == 0) write a 0                 // n is even
   ELSE write a 1                            // n is odd
   move pencil one position to the left
   n = n / 2                                 // integer division
}

Our Turing machine mimics this algorithm. We associate a meaning with each state to assist our explanation.

The Turing machine first determines whether there are an even or odd number of A's by alternating between the states labeled even and odd. It "crosses out" every other A by overwriting them with X's. This has the effect of halving (integer division by 2, throwing away the remainder) the number of A's. After determining the parity, the Turing machine moves the head left until it reaches an empty cell. Depending on the parity, it writes a 0 or 1. This process is repeated until the number of A's is 0.

Turing machine implementation in Java. We encapsulate each of the main Turing machine components (tape, transition, control) using good OOP principles.

The tape. Program Tape.java is an ADT that represents an unbounded Turing machine tape. It supports the following operations: move tape head left, move tape head right, read the symbol in the current cell, and write a symbol to the current cell. To implement it, we use two stacks (one to store all of the symbols to the left of the tape head, and one to the right). To print out the contents of the tape, we print out the reverse of the first stack, the current element, then the second stack.
The states. Each state has a name and a type (halt, left, right, accept, or reject).
The transitions. Each transition has the name of the initial state, the name of the final state, and the symbol to be written to the tape.
The Turing machine. We implement a Turing machine as a tape, a symbol table of states, and a symbol table of transitions.

Non-terminating Turing machines. From a theoretical standpoint, we are primarily concerned with machines that perform finite computations and then halt. However, many practical applications involve programs that are designed never to terminate (operating system, air traffic control system, nuclear reactor control system) or or produce an infinite amount of output (web browser, program that computes the digits of π = 3.1415...). The Turing machine model of computation extends to handle such non-terminating situations as well.

Exercises

What does the following Turing machine do when started with the given tape ...
Create a Turing machine that takes as input two binary integers, separate by a # character, and accepts the input if the first string is strictly less than the second.
How many steps does the Turing machine in the previous question take to compare two N-bit integers?

Creative Exercises

Langtons Ant. Write a program LangtonsAnt.java that simulates a two dimensional Turing machine known as Langton's Ant, and animate the results using Turtle graphics.
Turmites. Create some other two dimensional Turing machines or Turmites that produce interesting patterns.