Information Technology Reference
In-Depth Information
Although processing is not very complex, on the surface the states of a Turing
Machine may seem far from intuitive. Although formal processing by Turing
Machines depend solely upon the table to guide what happens next, the de
veloper of the Turing Machine usually motivates the states through an under
lying idea.
To learn the idea of the states for this Turing Machine, let's look carefully at the
table: The machine begins in state A and moves back to state A if an even num
ber of 1's have been processed so far. Similarly, the machine proceeds to state B
if cumulatively it has encountered an odd number of 1's. By keeping track of
whether it is in state A or B, the Turing Machine has recorded whether the num
bers read so far on the tape include an even or an odd number of 1's. With this
information, the table of the Turing Machine identifies the appropriate activity
when the machine encounters the space at the end of the number; according to
the table, the Turing Machine writes the required parity bit on the tape and then
moves to state C.
Because Turing Machines can seem abstract, understanding their processing of
ten is aided by walking through an example. To better understand how this
Turing Machine works, suppose that the number 10101 appears on a tape, as
shown at the start of Figure 7.1.
As specified, this Turing Machine begins in state A, and the readwrite head is
positioned at the left digit of our input 10101. For the first step, the machine
reads the input symbol (the digit 1) and then consults the table. In state A with
input 1, the machine is to write a 1 to the tape (not changing what is already
there), move its readwrite head to the right one character, and go to state B for
the next processing. The resulting configuration is shown as the second entry in
Figure 7.1.
For step 2, the machine reads the next input symbol (the digit 0), and again con
sults the table. This time, the machine is in state B with input symbol 0, so the
machine puts a 0 back on the tape, moves the readwrite head one character to
the right, and stays in state B. The resulting configuration is the third entry in
the figure.
For step 3, the machine reads the 1, consults the table, prints the 1, moves right,
and goes back to state A.
In step 4, the machine reads a 0, prints the 0, moves right, and stays in
state A.
In step 5, the machine reads a 1, prints 1, moves right, and moves again to
state B.
In step 6, the machine encounters a space or blank. Consulting the table for
state B, the machine adds a 1 to the tape, moves right, and enters state C.
In step 7, the machine stops, and processing is complete.
