Problem Solving in Automata, Languages, and Complexity

298 COMPUTATIONAL COMPLEXITY

To satisfy these requirements, we design the machine M* to simulate, on

input w, the computation of M, (w) within space s2 (lwl), and accept zu if and

only if A&, does not accept 20.

There are several issues in this approach which did not occur before in the

diagonalization proofs of Section 5.3:

(1) How do we make sure that A&* works within space bound sz(n)?

(2) How do we enumerate all DTM’s A&, with space bound s1 (n)?

(3) Is the space bound s2 (n) large enough for AJ* to simulate all M, with

space bound s1 (n)?

(4) What happens if A&, does not halt within space bound q(n)?

To solve question (1) we note that s2(n) is fully space-constructible, and

so we can construct M* in such a way that it first reads the input UI, and

then simulates a s2 (n)-space marking machine to mark off s2 ((w I) cells in the

work tape. It then begins to simulate Mw on w, using the input u) as both the

code of Mw and the input u), and using the s2 (1~11) marked cells to simulate

the work tape of M,.

For question (2)‘) we observe that the enumeration of DTM’s presented

in Section 5.1 can be easily modified to enumerate all standard one-worktape

DTM’s. More precisely, we note that each instruction of a one-worktape DTM

is of the form

S(qi 7 aj j ajl) = (qk&.,Dh,Dh’),

which indicates that if the machine is in state qi, reading a symbol aj from

the input tape and a symbol ajl from the work tape, then it changes to state

qk, writes al over the symbol ajl, moves the input tape head in the direction

Dh, and moves the work tape head in the direction &I. This instruction can

be encoded by the string

Then, the whole DTM can be encoded as

1” code1 code2 l ** cadet 11

for any nz > 1, if it has t instructions.

Now, suppose that sl(n) is also a fully space-constructible function, then

we can also attach a sr(n)-space marking DTM M with Mw to control its

space usage. However, this is really not necessary, because we need to satisfy

the requirement R, only for those Mw which do have space bound s1 (n). In

other words, we can simply simulate M, within space s2 (Iwl), and if Mw visits

more than s1 (lull) cells, then the requirement R, is automatically satisfied.

So, this brings us to question (3): C an we satisfy the requirement R, when

Mw does work within space bound sl(n)? We first note that the set of tape

symbols for M * is fixed, but the set of tape symbols for Mw varies as u, varies.

Suppose that M* uses tape symbols 0, 1 and B. Then, all tape symbols of