Problem Solving in Automata, Languages, and Complexity

4.3 Multi-Tape Turing Machines^185

tape 1

head 1

tape 2

head 2

tape 3

head 3

Figure 4.14: The TM A&

Next, we present a simulation of a multi-tape DTM by a two-way DTM.

Theorem 4.13 Every function computed by a multi-tape DTM is Turing-

computable.

Proof. Assume that M is a i&tape DTM, where k > 2. We are going to

describe how to construct a two-way one-tape DTM My to simulate AL Sup-

pose that the tape symbol set of M is I. Then we use the tape symbol set

rl = (I’ x {X,B})” U c for M 1, where X is a symbol not in I’. This means

that we divide the single tape of Mr into 2k tracks which form k groups. Each

group contains two tracks: one uses the tape symbol set I’, the other uses the

tape symbol set {X, B}. Thus, the blank symbol in I?r is

ii= [B,...,B]. \ /

2k

Each group records the information about a tape of A&, with the symbol X

in the second track indicating the position of the tape head, and the first

track containing the corresponding symbols in that tape of M. For instance,

Figure 4.14 shows the machine A&l that simulates a three-tape TM AL Its

tape contains the information of the following tape configuration of &?:

(0~10101,0011110,1100110). - -

Initially, we assume that the input is stored in the single-track form:

(s, x1x2 l l l -Ji),

where each xi, 1 < - i < - n, is a symbol in C. Machine Mr first sets up the tape

into the 2lc-track form to get the initial configuration

(SI, [xl, B,... , B] [x2, B,. l l , B] l l l [xn, B, l.. , B] [B, x, B, x,... , B, X] [B,... , B]).