Problem Solving in Automata, Languages, and Complexity

4.3 Multi-Tape Turing Machines 187

61 (Q?y?, [a, x, b, B, c, xl) = (Qayc, [a, x, 4 4 c> Xl> L)T

s (4 I x??, [a,B,b,X,c,X]) = (qxbc, [a,B,hX,c,X],L),

61 (q???, [a, x, b, x, c, xl) = (qabc, [a, x, b, x, c, Xl> 0

The first stage is done when A& reaches a state q&c, with a, b, c E I’. For
the second stage, l& will use the following set of states:

It begins with q&c and ends with q6ic if the instruction of &! to be simulated

is of the form:

q!l, (a, b, 4) = (P, (a’, b’, c’), (a, D2, D3))* (4. 1)

Here, we only present a more specific example. Instructions for other cases

can be constructed in a similar way.

Assume that & is in state q&c:, with a, b, c E I, and is to simulate the

instruction (4.1) with D1 = R, D2 = D3 = L. In addition, assume that the

relative positions of the three X’s in tracks 2, 4, and 6 of the tape of Ml are

like those shown in Figure 4.14; that is, the symbol X in track 2 occurs to the

left of the symbol X in track 4, and the symbol X in track 4 occurs to the

left of the symbol X in track 6. For this type of tape configurations, M1 has

the following instructions. (The following instructions apply to all U, v, w E I’

and all tl, t2, t3 E {B, X}.)

61 (qabc, [% B, v~ BY we BI) = (qabc, [%B,v,B,w,B],R)>

61 (qabc, [a> x, % B~ we B3> = (qabc,[a’,B,v,B,w,B],R),

61 (‘&ibc, [u, B, VT h we t31) = (qiibc, [U,X,‘@l,‘02], L),

h(qiibc, [U,tl,‘?B,w,B]) = (qtibc, [U,tl,V,B,w, B],f&

h(%bc, [U&J boxy w~BI) = (q&y [~,~l,b’,B,w,Bl,L),

Q&,, [%tl,~Awq = (q&J [Ql, v, 0-4B1, R),

6 (a^1 &, [u, t1, v,t2> WJI) = (Q&, [VI, v,t2/w31, fq,

s^1 (4 &‘[U,tl>V,t2~C,q = (Q&j [U,t1/02,031,L),

6 1 (4 &Y [u,m4t294B1) = (Q&, [U,h, 02, WJl, f-9,

s^1 (4 &, [u,t1, v, t2, w31) = (p???, [U,tI,v,t2,W, t3l~R)-^0

A multi-tape DTM can have any large number of tapes, but the number k

of tapes has to be a constant independent of the input size. What happens if

we allow an arbitrarily large number k of tapes, without a predenned bound

on Ic? This new type of machine is, then, more powerful than one-tape DTM’s.

In fact, such machines can accept any language.