Problem Solving in Automata, Languages, and Complexity

(1 ) M’ writes 1 on the work tape and moves its tape head to the right of

this symbol 1. M’ also moves its tape head of the input tape to the

leftmost symbol of the input.

(a ) M’ uses the work tape to simulate the (n+2)2-clock DTM M of Example

6.18. Meanwhile, the input tape head moves simultaneously from the

leftmost input symbol toward ri.ht.

We also note that the machine J4 visits exactly n + 2 tape cells. cl

302 COMPUTATIONAL COMPLEXITY

head is n + 3: Each input symbol 1 causes the tape head to move one round;
it takes one round to find out that there is no more symbol 1 left, and two
more rounds to finish. Therefore, the total number of moves by A4 is exactly
(n + l)(n + 3) + 1 = (n + 2)“. (Th e extra one move is taken to move from
state q6 or q8 to the final state h.) That is, M is a (n + 2)2-clack DTM.
For instance, if the input is 14, then the computation of A4 is as follows (the
number k shown in I-’ indicates the number of moves from one configuration
to the next):

(qo, 1lllB) l-l (4111111) t-l (q2, llla) t-3 (42,Bllla) t-l (q3,Illa)

l--l (44,alla) t-3 ( q4, alla!) t--l (a, alla) l--l (q1, alla> t-l (q2, .m)

t-2 (42,BalU~) t-5 (q 4, UUUUIJ) k5 (41, I&luau) t-l (45, gzuu)

b4 (95, au&i!) b1 (Q6, aaat$ t-4 (q6, Buaaa) t-l (h, aaaa).

Example 6.19 Show that [fil is fully space-constructible.

Solution. We construct a standard one-worktape DTM M’ as follows:

(3) If the input tape head is scanning a blank symbol when the simulation

of M halts, then M’ halts; otherwise, M’ moves the head of the input

tape to the leftmost symbol of the input, adds an extra symbol 1 to the

work tape, moves the head of the work tape to scan the blank to the

right of the rightmost symbol 1, and goes back to step (2).

Suppose M’ halts when the work tape holds k symbols 1, then we know
that the input length is less than or equal to (lc+2)2 and greater than (Ic+1)2.
In addition, we observe that the (n +2) 2-clack DTM M of Example 6.18 visits
exactly m + 2 cells on input lm. Thus, M’ visits exactly [fil cells.^0

Now we present some applications of the hierarchy theorems.

Example 6.20 P $ EXP.

Proof. Note that, for any fixed integer i, ni + 2’Y That is, ni < 2n for
sufficiently large integers n. Therefore, by the linear speed-up theorem (and
Example 6.11), DTIME(r-8) C - DTIME(2”). Furthermore, if tl(n) = 2” and