Information Technology Reference
In-Depth Information
The Turing machine is fully defined by these three functions, which can be written out as a table of
quintuples
.
This is just a fancy name for the set of these two variables and three functions we have defined: Qi
i
and S
i
at time T and Q
j
, S
j
, and D
j
at time T + 1. All we have to do now is write some data on the tape and start the
machine at the right position. The machine will then calculate away and print out the result of its calcula-
tion somewhere on the tape for us to look at when the machine has finished. Note that we have to explicitly
instruct the machine when to halt. This sounds pretty trivial but we will see later that the issue of whether
a machine will halt or not leads to a profound issue in the theory of computation.
Let's try to construct a very simple Turing
machine that measures the
parity
of any string
of 0s and 1s. The parity of a string is defined to
be whether the number of 1s is even or odd. We
are given the string 1101101, and begin by writ-
ing this binary string as input data on the tape as
shown in
Figure 6.8
, with one symbol in each box.
The reading head of the machine starts at the far
left of the string, on the first digit. The end of the
string is designated by the letter E. On either side
of the string there are only zeros on the tape.
Before it has read any symbols, the machine starts off in state Q
0
, corresponding to even parity. If
the machine encounters a 0, it stays in the state Q
0
- because the parity has not changed - and then moves
one space to the right. If the symbol it reads is a 1, the machine erases this, replaces it with a 0, moves one
space to the right and changes to the state Q
1
. This is the state for odd parity. Continuing, if the machine
now hits a 0, it stays in the state Q
1
and moves another space to the right. If it hits a 1, it erases it, prints a
0, and moves another cell to the right, changing the state back to Q
0
. The machine continues working along
the string in this way, changing state whenever it encounters a 1, and leaving a string of 0s behind. If the
machine is in the state Q
0
after it has read the last symbol, the string has even parity; if it is in the state Q
1
,
the parity is odd.
How does the machine tell us the parity and the result of its calcu-
lation? We need to include a rule that tells the machine what to do when
it meets the end symbol E. If it is in state Q
0
and reads E, it erases the E
and writes a 0 meaning that the string had even parity. If it is the state
Q
1
, it replaces E by a 1 meaning the string had odd parity. In both cases
the machines enter a new state Q
H
, meaning “halt.” It does not need to
move to the right or the left: the answer can be observed by looking at
the box on the tape where the machine halted (
Fig. 6.9
).
To understand what happens, we have pains-
takingly described the operation of this Parity
Counter Turing Machine in words. In practice, it
is more economical to summarize the machine's
behavior as a table of quintuples. We can summa-
rize this table of quintuples in a diagram (
Fig. 6.10
).
Here we have indicated the states Q
0
and Q
1
- Even
and Odd - by the circles and the direction of motion
after reading the box, by R, for right which we also
write in the circle. The directed arcs, starting with
either a 0 or 1 on them, indicate what happens to
…001101101E00…
Start
Fig. 6.8. Input tape for the Parity Counter Turing Machine.
…0 001…
{Even (0), or Odd (1)}
Fig. 6.9. Output tape from the Parity
Counter Turing Machine.
{0, R}
{0, R}
{0, R}
{0, R}
{0, R}
1
1
0
0
0
E
E
E
E
E
E
Start
Start
Halt
Halt
Odd
Odd
Odd
Even
Even
0
0
1
{0, R}
{0, R}
{0, R}
{0, R}
Fig. 6.10. Diagram of a Parity Counter Turing Machine.
Search WWH ::
Custom Search