6.2 Time and Space Complexity 291
011001
Ltll^4
Figure 6.3: A local configuration.moves left to cell g, then moves left to read the symbol of cell e, and finally
moves back to the original cell g. After the bee-dance, the local configuration
of M’ contains all symbols in the three cells of M’ (corresponding to 3m cells
of ML
(5) When the local counter of M’ is equal to 4, M’ simulates M on the
local configuration for as many moves as possible. That is, it simulates M
on the local configuration until one of the following conditions occurs: (a) M
halts on the local configuration, (b) M enters a same local configuration the
second time (thus, M enters an infinite loop), or (c) M tries to move out of
the 3m cells of the local configuration. In case (a), M’ simply halts. In case
(b), M’ enters an infinite loop. In case (c), M’ changes its local configuration
Q to the configuration p right before the tape head of M moves out of the 3m
cells. Note that the change from a to ,0 takes only one move for M’, since
this change occurs internally in the local configuration and can be simply
encoded in the transition function of M’. On the other hand, this change of
configuration takes at least m moves for M since the tape head of M must
move from group g to the right end of group r or to the left end of group e.
(6) When the local counter of M’ is in {5,6,7,8}, M’ does a second bee-
dance to copy the new symols of its local configuration to the cells e, r and g
on its tape.
(7) Finally, when the local counter of M’ is equal to 9, M’ moves its
tape head to one of its neighbor according to the tape position of its local
configuration.
We show, in Figure 6.4, an example of such ten moves, which simulate theconfiguration change of M from (q,OOQlll) to (p, 111000).
It is clear that the above simulation is correct and sck(M’) = L(M). In
addition, for x E L(M), M’ uses ten moves to simulate at least m moves of
M, before it halts. We note that, in the initialization stage, it takes n moves
to copy the input to the second tape, in the group form, and it takes [n/ml
moves to reset the tape head at the rightmore input group. Also, in the halting
stage, M’ halts at the fifth move within that simulation step. Therefore, we
see that M’ has a time bound of
<n+F+lO+-+16. e-9
m m