Problem Solving in Automata, Languages, and Complexity

4.3 Multi-Tape Turing Machines 183

additional instructions:

B’(qb, B) = (q;, [B,$ -f% S’(q;, B) = (qb,B, L),

S’(qt,B) = (q;> [B,%R), 6’(& B) = (qt, 4 L)Y

where qd, and qi are new states in Q’ - Q. In addition, if machine A&’ reads

the symbol $, then it needs to change track. That is, for each q E Q, M’ has

the following additional instructions:

6’(qbr$) = (q&R), s’(qt$) = (qbJsjR)*

Finally, if machine M reaches hb or h t, it restores the tape into the one-
track form and halts. More precisely, it needs to first move all nonblank
symbols (those in both the top track and the bottom track) to the bottom
track starting from cell Ci, and then eliminate the top track (see Exercise 1
of this section).
From the above sketch, we have obtained the following theorem.

Theorem 4.11 (a) Every function that is computed by a two-way infinite

one-tape DTM is Turing-computable.

(b) Every language that is accepted by a two-way infinite one-tape DTM is

Turing-acceptable.

Next, we extend Turing machines to multi-tape DTM’s. For each k > 2, a
k-tape DTM is similar to a two-way DTM with the following exceptions:

(1) It has k two-way infinite tapes. Each tape has its own head. All heads
are controlled by a common finite control. There are two special tapes, an
input tape and an output tape. They hold the input string and the output
string, respectively. The head of the input tape can only read and cannot
erase or write symbols. (Such a tape is called a read-only tape.) The heads of
other tapes can read, erase and write symbols. Figure 4.13 shows a three-tape
DTM.

(2) In each move, a head in a multi-tape DTM can stay (denoted by S) at

the same cell, without going to the right or to the left.

The transition function 6 of a k-tape DTM is a function mapping Q x I”

to (Q U (h)) x I” x {L, R, S)“. An instruction

qq, (a17 a27 l ’ - 7 ak)) = (p, (h, b2, l l. , bk), (01, D2, 9 l .Y Dk>>,

where Di E {L, R,S}, for i = 1,. .., k, means that if the control is in state q
and the head of the ith tape reads the symbol ai, for i = 1,... , k, then the
head of the ith tape will write bi over ai, move in the direction Di, and the
control will change to state p.
A configuration of a &tape DTM is just the state plus k tape configurations,
each of the same form as that of a two-way DTM.
A multi-tape DTM can often reduce the work of a one-tape DTM dramat-
ically. The following is an example.