Information Technology Reference
In-Depth Information
the number of states small in our Turing machine. Similar examples
using decimal numbers are possible; although the format of such
numbers might be more familiar, the corresponding Turing machines
would be more complicated. (For example, the number of rows in
each table would increase by a factor of 5 if we considered decimal
numbers rather than binary numbers.) Please don't be intimidated by
the binary numbers! Remember, most real computers work by pro
cessing binary numbers, 0s and 1s, as we discussed in Chapter 2.
Example 1
Assume that this Turing Machine has its readwrite head at the left end of a binary
number. The machine processes the number from left to right and then adds a 0 or 1
at the location following the number, so that the total number of 1's is even; that is, if
the number has an even number of 1's already, then the Turing machine adds a 0 to
the right of that number, but if the number has an odd number of 1's, then a 1 is
added. (In case you care, this extra digit is called a
parity bit
and is important in check
ing the storage, retrieval, and transmission of data. We will have a chance to discuss
this further in a later chapter.) Here is the description of what this Turing Machine does
to place a 0 or 1 as the appropriate parity bit at the end of the binary number:
Possible symbols on each location of the tape: 0, 1, space where “space”
means that the tape is blank at that location
Starting state: A
Ending state: C
(The Turing Machine also has a state B, corresponding to an intermediate
point in computation, but state B neither begins the computation nor ends it.)
Processing Table
Current State
Input
Symbol
Tape Head
Next State
Written
Movement
to Tape
A
0
0
Move right 1 character
A
A
1
1
Move right 1 character
B
A
space
0
Move right 1 character
C
B
0
0
Move right 1 character
B
B
1
1
Move right 1 character
A
B
space
1
Move right 1 character
C
C
0
stop
C
1
stop
C
space
stop
