180
10
4.3
TURING MACHINES
(a) Consider the language L1 over the alphabet (C U {B}) x F, where
F is the set of all partial functions from Qr to &I, with w =
[so, go] [sl, gr] l l. [s,, gn] E L1 if and only if for all i = 0,... , n,
gi = fi, with respect to machine M and string sosl.. ‘sn. (Note:
If IQ11 = m. then there are at most UP+’ symbols in F, each
encodes one partial function from &I to Ql.) Show that there
is a read-only DTM Ml that accepts L1; that is, show that a
read-only DTM can check whether each symbol gi stored at the
second track of cell Ci encodes correctly the function fi. [Hint:
Ml cannot simulate M step-by-step to check whether the values
fi (4) are correct, because Ml does not have a pebble and so once it
leaves cell Ci, it cannot remember where it is. Instead, Ml needs
only to check the consistency of the function ji with its neighbors
fi-1 and fi+l, similar to the problem of checking the consistency
of neighboring crossing sequences in Theorem 4.10.1
(b) Let L2 be the language over the alphabet (C U {B}) x F such
that w = [SO, go] [sl, gl] l l l [s,, gn] E L2 if (1) w E Ll defined in
part (a) above, and (2) the one-pebble DTM M accepts the input
tot1 l l l tn, where t; = si if si # B and ti = & if si = B. Show that
there is a read-only DTM M2 accepting L2. [Hint: M2 uses the
information g; to simulate M as follows: If M holds the pebble in
its state (i.e., if M is in a state q*), then M2 simulates M step-
by-step. If M puts down the pebble in Cell Ci, then M2 uses gi
at the second track to determine the state it will change to when
it returns to cell Ci.]
(c) Show that if M is a one-pebble DTM, then L(M) is regular. [Hint:
Show that the language L(M) is the image of a homomorphism 4
on L2; see Example 2.35.1
. We consider another extension of read-only DTM’s. A DTM M is called
a read/erase-only DTM if it can, at each move, only read an input
symbol and/or erase it (i.e., replace the original symbol by B). That is,
a DTM M = (Q, C, I’, S, s) is a read/erase-only DTM if I’ = C U {B},
and the transition function S satisfies the following property: For any
4 E Q and a E C U {B}, 6(a,a) is either (p,a, D) or (p,B, D) for some
p E Q and D E {L,R}.
(a) Show that there exists a read/erase-only DTM that accepts the
language L = {unbncn 1 n > - 0).
* (b) Show that there exists a Turing-decidable language that is not
accepted by any read/erase-only DTM.
Multi-Tape Turing Machines