6.3 Hierarchy Theorems 299
A&, have to be encoded by strings over (0, 1). We recall that, in Section 5.1,
the universal DTM U uses OliO to encode the ith symbol of A&. A more
economical way is to use the ith binary string of length [log!] to encode the
ith symbol of A&,, where t is the number of tape symbols in A&,. Thus, each
symbol of A&, becomes a string of length [log tl in M. It means that M
needs space [log t]sl (Iwl) t o simulate the tape configuration of A&,.
In addition, we note that &! uses input u) both as the machine code of
Mw and the input w and, hence, it cannot directly simulate Mw. Instead,
M needs to store the current state and the current position of the input tape
head of Mw in its work tape. This takes [log al + [log nl < 2rlog nl cells,
where Q is the number of states in Mw. Furthermore, M needs up to [log nl
cells of scratch space in a separate work tape to compare a tape symbol or a
state symbol in its work tape (written in the binary form) with a tape symbol
or, respectively, a state symbol in its input tape (written in the unary form).
Note that logn < - sl(n). Thus, altogether, we need to make sure that
We note that, although liminf,,, sl(n)/sz(n) = 0, the above inequalitydoes not always hold, since t varies as w varies. This problem is solved by
the fact that each DTM has an infinite number of machine codes. Indeed,
for sufficiently large n, each DTM has a code of length n. Now, from the
assumption of lim infn,, sl(n)/s2(n) = 0, we know that for any integer
t > 0, there exists an integer n such that [logtlsl(n) 5 sz(n). Consider a
machine code w’ of length n such that Mwl = Mw. Then, inequality (6.1)
holds with respect to 20’ and so the simulation of Mw/ by M”, in stage w’,
can be done in space s2( jw’l), and requirement R,I can be satisfied. Since
L( Mw ) = L( Mwl), as long as the requirement R,I is satisfied, the requirement
R, is also satisfied.
Finally, let us consider question (4). Suppose that Mw does not halt on
input w and it works within space s1(Iwl). Then, it must eventually enter an
infinite loop, and some configuration would occur more than once. However,
we cannot find this infinite loop by checking the history of the computation
as we did in Example 6.15, because that might take too much space.
An alternative way is to count the number of moves in the simulation. As
shown in Example 6.15, if a DTM M works within space bound s(n), then
it has at most f(s(n)) = q(n + l)s(n)P@) different configurations. So, if M
runs for more than f(s(n)) moves within space s(n), some configuration must
have occurred twice and we know that M does not halt. This means that M*
only needs to use at most log(f(sl(n)) ce 11 t s o write down the number li’ of
moves taken so far (in another separate tape) in order to determine whether
Mw has entered an infinite loop or not. We note that q < - n, and so
log(f(s1(n)) 2 logs1(n) + 2logn + (W)s1(n) 5 (W + 3)s1(4,since sl(n) > - logn. Now, we can find, for each 20, a code w’ with large Iw’I
such that Mwi has exactly the same instructions as Mw and log( f (s1 (Iw’l)) 5