4.2 Examples of Turing Machines 179
* 8. We consider an extension of read-only DTM’s. A one-pebble, read-only
DTM (or, simply, one-pebble DTM) is a read-only DTM AL+! with the
additional capability that it can mark a specific cell of the input tape
by putting a pebble on it. The machine M has only one pebble, and
so at any time the tape can have at most one marked symbol. More
precisely, a one-pebble DTM M is a DTM M = (Q, C, I’, 6, s*), where
Q=Qlu(q* ~q~Q~}forsomefinitesetQ~,I’=C~{~}~{a* JUEC
or a = B}, s E &I, and S satisfies the following properties: For any
q E Ql and a E C U {B),
(i) d(q, a> = (p, a, D) for some p E Q1 and D E {L, R}.
(ii) s(4, a) is either (p, a, D) or (p*, a, D) for some p E Q1 and D E
(L, RI*
(iii) J(q, a) is either (p’, a, D) or (p, u, D) for some p E Ql and D E
(L, w
(iv) 6(q, a) is undefined.
(In the above, the superscript * denotes the pebble. So, a state Q*
indicates that M is holding the pebble at its finite control, and all tape
symbols are unmarked; and a state 4 E Qi indicates that the pebble is
in an input cell. Note that property (i) indicates that M cannot mark
a cell if it does not hold the pebble in its finite control now.)
(a) Construct a one-pebble DTM M such that on each input x of
length n > - 2, M halts in exactly n2 moves.
(b) Show that for each read-only DTM A&, there exist two constants
c and d such that if M halts on an input 1~: of length n > - 1, then
it must halt within cn + d moves.
(c) Show that for each one-pebble DTM M, there exist two constants
c and d such that if M halts on an input x of length n > - 1, then
it must halt within cn2 + d moves.
(d) Show that if L is a regular language, then there is a one-pebble
DTM M that accepts the language SQRT(L). (Recall that
SQRT(L) is defined in Example 2.44 as {z 1 (3-J 11 = IX,ZXJ E
Jv. >
* 9. In this exercise, we prove that the language accepted by a one-pebble
DTM must be regular. Assume that M = (Q, C, I, 6, s*) is a one-pebble
DTM with Q = &I U {q* I 4 E &I}. Also assume that M operates on
an input x and visits cells Co, Cl,... , Cn, with symbol si in cell Ci,
for i = O,l,.. .,n (i.e., sosl ..*sn = BxB l -B). For each i, 0 < i < n,
define a partial function ji : &I + &I as follows: If S(q, ST) = (p, s2fiD)
for some p E &I and D E {L, R}, then fi(q) is the next state Y E &I
(Y # h) at which M re t urns to cell Ci. Otherwise, fi(q) is undefined.
That is, the function fi encodes the states of M when it visits cell Ci
with the pebble in cell Ci ( similar to a crossing sequence of a read-only
DTM). Note that fi depends on both machine M and input X.
