specifies what happens on all the tapes. For example, if n = 2, with a current
configuration shown in Figure 10.8, then
δ (q 0 , a, e) = (q 1 , x, y, L, R)
is interpreted as follows. The transition rule can be applied only if the machine is
in state q 0 and the first read-write head sees an a and the second an e. The
symbol on the first tape will then be replaced with an x and its read-write head
will move to the left. At the same time, the symbol on the second tape is
rewritten as y and the read-write head moves right. The control unit then changes
its state to q 1 and the machine goes into the new configuration shown in Figure
10.9.
To show the equivalence between multitape and standard Turing machines,
we argue that any given multitape Turing machine M can be simulated by a
standard Turing machine and, conversely, that any standard Turing machine
can be simulated by a multitape one. The second part of this claim needs no
elaboration, since we can always elect to run a multitape machine with only one
of its tapes doing useful work. The simulation of a multitape machine by one
with a single tape is a little more complicated, but conceptually straightforward.
Figure10.8
Figure10.9