4.3 Multi-Tape Turing Machines 189
- Describe the details of a simulation step of the two-way DTM &+!I of
Theorem 4.13 that simulates a three-tape DTM AL That is, show the
instructions of A&l that move the head to left to collect the tape infor-
mation of M and then move right to execute an instruction of M from
this information. - Given a two-way infinite one-tape DTM M with C = (1) and I’ =
(0, 1, B}, construct a multi-tape DTM M’ that, on input ( ln, 1”)) sim-
ulates M on input 1” for at most k moves so that it halts if and only if
M halts on input ln within k moves. - Construct multi-tape DTM’s to accept the following languages. For each
language, discuss how much time your machine saves over a one-tape
DTM using the same algorithm.
(a) {w E {a$}* 1 w = We}.
(b) {(%~2) I a+2 E {~,~}*,21
(c) {unbncn 1 n > - 0).
(cl) {a”bnck 1 m,n, k > 0,m # n(4 {w E 1% b, c)* I #,(w) = #b(is a substring of 22).ornfkorkfm}.4 = #c(w>~*- Construct multi-tape DTM’s to compute the following functions. For
each function, discuss how much time your machine saves over a one-
tape DTM using the same algorithm.
(a) f(z) = xR on strings x E {a, b}*.
(b) f b-4 4 = nm on natural numbers m, n.
(C) f(nl, 722,... , nk) = max{nl, n2,... , nk) over positive integers nl,
l l l 7 nk, where k is not fixed.
(d) .f(nl, 732, l l .Y nk) = the maximum number of occurrences of a
positive integer in (121,... , nk), where k is not fixed. (E. ., g
f(3,5,3,6,7) = 2 and f(3,6,3,6,6,5,6) = 4.
0 e sort(n
order,1, n2,... , nk) = the li st (721,..
where nl,... , nk are positive’ 7 nk) sorted
integers andin the increasing
k is not fixed.- A two-dimensional DTM M is a TM whose “tape” is a two-dimensional
plane divided into infinitely many cells (see Figure 4.15). A two-
dimensional DTM M operates in a way similar to a two-way DTM
except that in each move, it can move its head up (U), down (D), left
(Q 7 right (R) or stay (S). Initially, the input is stored in a horizontal
row and the head is scanning the blank cell to its right. When it halts,
the output is also stored in a horizontal row (but not necessarily the
same row as the input) with the head pointing to the blank cell to its
right. All other symbols not on this row are ignored.