184 TURING MACHINES
Figure 4.13: A three-tape DTM.Example 4.12 Find a three-tape DTM M that computes the function
f (n, m) = n. m on natural numbers n and m.
Solution. Following the convention of Section 4.2, we assume that initially
the tape configuration of the input tape is InBY’%, and all other tapes have
only blanks. That is, the initial configuration of M may be described as
(s, l”Blm13,B, B). - w e need to construct a DTM A& such that the final config-
uration of tape 3 is Pm- B. The algorithm of M is as follows:
(1) Copy P to tape 2.
(2) For each symbol 1 in tape 2, delete it and copy 1” from tape 1 to tape 3.
When tape 2 is empty, halt with output in tape 3.
In the following, we present the transition function S of M:
w (B7 4 B)) = (Ql, (B, B, B), (L s, S)),
~(Q1~w4B)) = (s1,(1,l,B),(L,R,S)), qql,(wvq) = (q2,(B,B,B),(S,L,S)),
qs2, (BY 17 B)) = (a37 (B, B, B), (L, s, S)), qq2, (BY B, B)) = (h, (4 B, B), (S, s, S)),
~(q3,(1,B,B)) = (q3,(1,B,l),(L,S,R)), &o,(B,V)) = (q4,(B,B,B),(fWS)),
s(Q4, (W,B)) = (a, (l,B,B), (6% s)), +nr (BAB)) = (w, (VJ), (s, L, s)).We show its computation on input (2,3) as follows:(s, llBlllB,B,B) t- (41, llBlll,B, B) - t- (91, llBll1, - lB, - B)
I-* (ql, llB111, lllB,B) t- (q2, llglll, l&B) t- (q3, llBll1, ll& B) -b (q3, LlBlll, llB, 1B) 1 (q3, BllBlll, lll3, llE3) i- (q4, LlBlll, llB, 1lB) -
p (q4, 11~111, ll& 11B) I- (qa, llB111, 11, 1lIJ) p (qz, 11~111,~,~U~B) -
p (q2, llBlll,& llllllI3) I- (h, llBlllJ, 1lllllB). -
We remark that the total number of moves by the above multi-tape DTM
M to compute n l m is O(nm), whereas a one-tape DTM using the same
algorithm would take O(m2 n) moves. cl