290 COMPUTATIONAL COMPLEXITY
tape in the simulation, if the initial internal position of the work tape head
of AP is at the middle of the group (so that the work tape head of M cannot
move out of this group in less than m/2 moves). Therefore, the total space
used by M’ is bounded by max{ 1, c l s(n)}.^0- Theorem 6.10 (Linear Speed-Up Theorem) Szsppose limn,, t(n)/n = 00.
Then, for any constant c > 0,
DTIME(t(n)) = DTIME(c. t(n)).Proof. Again, we only need to prove the theorem for 0 < c < 1. Let A be a
set accepted by a k-tape DTM M with time bound t(n). We will show that
A is also accepted by a (Ic + 1)-tape DTM M’ with time bound c l t(n). The
idea of the proof is to group together a sequnce of moves of M and simulate
the effect of these moves in a constant number of moves. In order to do this,
we need to group some tape cells into one, as we did in the tape compression
theorem.
We descirbe the new DTM M’ in the following. To simplify our explana-
tion, we only consider the case of k = 1. The general cases are similar.
(1) Let m be a positive integer satisfying m > 10/c. We combine m. tape
cells in the tape of M into a single cell for A!P. Thus, each tape symbol of M’
is a member of I’“, where I’ is the set of tape symbols of M. In particular,
M’ first encodes each group of m, input symbols into one tape symbol and
puts them in the second tape. After this initialization step, M’ only works
on the second tape.
(2) Each state of M’ is a pair of a local configuration and a local counter,
where a local configuration consists of 3m cells of the tape of M, the head
position within these 3772 cells, and a state of M, and a Zocal counter is a digit
in (0, 1, l. l , 9). Thus, each state of M’ is of the form
where q is a state of M, al,... , asm E I’, and j E (0, 1,... ,9}. For in-
stance, (q, 011001; 5) re p resents the state of M’ whose local configuration is
that shown in Figure 6.3 and its local counter is 5. Note that there are at most
dm local configurations for some constant d. Therefore, M’ has a constant
number of states.
(3) Each simulation step of M’ consists of 10 moves, administered by the
local counter. That is, in each move, M’ changes its local counter from j to
j + 1, if 0 < j < 8, and from 9 to 0.
(4) In the fiit 4 moves (i.e., when the local counter is in (0, 1,2,3}), M’
reads the svmbols of the two neighbors of the cell it is scanning now. Let .Q
denote the cell currently scanned by the tape head, T denote the ryght neighbor
of g, and e denote the left neighbor of g. M’ reads symbols from these cells
by a 4-move bee-dance: It moves to its right to read the symbol of cell Y, then