172 TURING MACHINES
B/B, L jg k-i+3 T
cdB,R w
/
1
'\
B / CI, L
Figure 4.9: DTM M computing the function insert;.
Solution. We create two procedures:
Procedure R. This procedure moves a block of nonblanks to the right
by one square. More precisely, it works as follows: for any x, x E I’* and
Y E (r - w)*l
(s, xBy&) < (h, xBByz).
Procedure T. This procedure finds the next blank to the right. That is, for
any x:, x E I’*, y E (I’ - {B))’ and any c E r, it has the effect of
(s, xcyBz) F (h, xcyBz).
We leave the implementations of procedures R and T as exercises. Using
these two procedures, the DTM M for function f can be constructed as shown
in Figure 4.9. This DTM &? operates as follows:
(1) From state s to state 41, M inserts a blank B between the block xi and
the blank to its left. That is,
(s, BxlB l. •Bx~.-~Bx~B l. .BxkByE3)
tf (qI,BxlB~Bx~-lBBx~B~BxkBy~y~),
where y = YlY2 and lY21 = 1. (If Y = E, then the head is scanning the blank
to the right of xk.)
(2) From state 41, going through the loop once and back to state 41, the
configuration changes as follows:
(ql, BxlB l l .Bx~.-~Bz~Bx~B l l .B~~Bz~z~zs)
p (ql, BxlB l l .Bx~-~Bx~x~Bx~B l l .BxkBzl~),
where y = ~l~‘&@Xq and 1x21 = 1231 = 1.
(3) When y has been inserted between xi-1 and xi, M reaches the config-
uration
(ql, BxlB.. .Bx~-~B~Bx~B l. .BXkB)
and it halts.^0
