4.3 Multi-Tape Turing Machines 181
Figure 4.11: A two-way infinite one-tape DTM.to use, the class of Turing-computable functions remains the same. The proof
for this equivalence result amounts to a simulation of the multi-tape DTM by
a standard one-tape DTM.
First, we extend a one-tape DTM to have a tape that is infinite to the
both ends, called a turo-zuay-infinite one-tape DTlM (or, simply a tzuo-ulay
DTM). Figure 4.11 shows such a machine. A two-way infinite one-tape DTM
M = (Q, C, I’, S, s) operates in the same way as a one-tape DTM except that
its tape has no left end and so it is free to move to the left and never hangs.
Since the tape of a two-way DTM has no left end, its tape configuration
has a different representation. Assume that the tape contains
. l l BBBxayBBB - l l 9
with the head scanning the symbol a, and that the leftmost symbol of x
and the rightmost symbol of y are not B. Then, we write (x, a, y) or xay to
represent this tape configuration. For instance, the tape of Figure 4.11 can
be represented by abbuB.
When a two-way DTM iV computes a function, it writes the output any-
where in the tape and halts at state h with the head scanning the blank
symbol to the right of the rightmost symbol of the output. In other words, M
computes a function that maps input (xi,... , x,-J to the output (~1,.. ‘7 Y r-n >
if
(s, x~Bx~B l. .Bx,B) _ t-j-j (h, ylBy2B. l l By,B). -
Let us see how a one-tape DTM AP can simulate this machine M. The
main idea is to divide each tape cell of M’ into two traclcs and use these two
tracks to simulate the two halves of the two-way tape of M. To be more
precise, each cell of the tape of M’, except the leftmost one, now contains two
symbols from I’, one called the top symbol and the other called the bottom
symbol. The leftmost cell of the one-way tape of M’ contains a special new
symbol $, which indicates that this is the left end of the tape.
Now, let us fix a specific cell of the two-way tape of machine M, and call
this cell Co. Call the cells to its right Cl, C2,... , and the cells to its left