Consider, for example, the two-tape machine in the configuration depicted in
Figure 10.10. The simulating single-tape machine will have four tracks (Figure
10.11). The first track represents the contents of tape 1 of M. The nonblank part
of the second track has all zeros, except for a single 1 marking the position of
M’s read-write head. Tracks 3 and 4 play a similar role for tape 2 of M. Figure
10.11 makes it clear that, for the relevant configurations of (that is, the ones
that have the indicated form), there is a unique corresponding configuration of
M.
The representation of a multitape machine by a single-tape machine is
similar to that used in the simulation of an offline machine. The actual steps in
the simulation are also much the same, the only difference being that there are
more tapes to consider. The outline given for the simulation of offline machines
carries over to this case with minor modifications and suggests a procedure by
which the transition function of can be constructed from the transition
function δ and M. While it is not difficult to make the construction precise, it
takes a lot of writing. Certainly, the computations of given the appearance of
being lengthy and elaborate, but this has no bearing on the conclusion. Whatever
can be done on M can also be done on .
Figure10.10