4.2 Examples of Turing Machines 173
Read-Only Turing Machines. In Theorem 4.2, we showed that every
regular language is Turing-acceptable. We note that the DTM hl’ in that
proof never writes a new symbol over an original input symbol; that is, for
any q E Q and any a E I’, 6/(q, a) = (p, a, D) for some p E Q and D E {L, R}.
We call such a DTM a read-only DT2M. In the following, we show that read-
only DTM’s accept only regular languages.
*Theorem 4.10 Every language accepted by a one-tape, read-only DTM is
regular.
Proof. We first make a small change on our DTM model. We assume that the
one-tape, read-only DTM hl = (Q, C, I, 6, s) begins the computation with the
tape head scanning the leftmost cell of the tape. In addition, if M accepts
the input, then its tape head always moves from left to right when M enters
the state h. That is, we assume that the initial configuration of M on x
is (s, E&E), and that the only instructions entering state h are of the form
t5(q, a) = (h, a, R) for some q E Q and a E I’.
We note that this new DTM model is equivalent to the original model:
Given a DTM M of the original model, we can create a DTM M’ of the new
model that accepts the same language as M. Namely, M’ first moves to the
right, passing through the input until it finds the first blank symbol to the
right of the input. Then, it begins to simulate machine M. When M accepts,
M’ does not halt but makes one more move to the right and then halt in state
h. Similarly, given a DTM M’ of the new model, we can construct a DTM
M” of the original model such that L(M”) = L(M’). Therefore, this change
on the model does not affect the class of languages accepted by one-tape,
read-only DTM’s.
Now, let us fix a one-tape, read-only DTM M = (Q, C, I’, S, s) of the new
model. Since machine M cannot write new symbols on the tape, we may
assume that I’ = C U {B}. We will design an NFA M’ to simulate M. In
order to describe the NFA M’, we first need to define the notion of crossing
sequences. Let us call the cells of the tape of a DTM Co, Cl, C:!,.. l , with
Co indicating the leftmost cell of the tape. The crossing sequence between
cells Ci and Ci+l, for i > 0, in a computation path of M, is the record of
the moving directions andthe new states when the tape head moves over the
boundary between the cells Ci and Ci+l.
For instance, consider the following read-only DTM M:
0qAR
!LO,R
P, 0, R
OJ”1
PAR
411, R
t, 1, L
t, 1,LB
P, B, R
h,B,R
f,B, L