5.6 Undecidable Problems 267
(c) We need to show that A3 = ((2, y, i) 1 A& enters state qi in its
computation on input y} is not recursive. We reduce the halting problem
Iil() = {(X,Y) I b(Y) -11 to iti F or any DTM A& we modify A& into a new
DTM AP as follows: Suppose MX has states ql,q2,... , qn, where qn is the
halting state. Then, AP has states ql, q2,... , q,+l, where qn+l is the halt-
ing state. M’ has all the instructions of Mz plus the following additional
instructions:
S’(qn,a) = (q,+l,a, R), for all a E I’.
It is easy to verify that Max halts on y if and only if M’ enters state qn in its
computation on input y.
We observe that the program code x of M’ can be computed from program
code ;t= of Mx, since the modification of the code is quite simple. (Indeed, it
can be proved that this modification is a primitive recursive function.) Thus,
there exists a recursive function f such that M’ = Mf(,). Now, g((x, y)) =
(f (x)1 Y, maxstaqx)) is a reduction for li’o <m AS.
(d) We need to show that the set A4 of all program codes x for which the
computation of Mx on input 111 contains 000 in one of its tape congifurations
is not recursive. We reduce the halting problem K to Ad. For any string
y E C*, we let g denote the string that is obtained from y with each symbol
a E C replaced by the string Ba. (E.g., if y = 01100 then g = BOBlBlBOBO.)
For any DTM Mx, we construct a new DTM M’ as follows:
(1) M’ erases its input y and writes down i!BBi? on its tape. (Note: 2 is a
fixed constant to machine M’.)
(2) M’ simulates the universal DTM U on the initial configuration (ql, xBx)
with the modification that, at each move, it skips a blank symbol. That
is, when U moves right, M’ moves two cells to the right; and when U
moves left, M’ moves two cells to the left.
(3) If the simulation halts, then M’ enters a new state and writes down
three consecutive O’s and then halts.
By the Church-Turing Thesis, such a DTM M’ exists and, furthermore, can
be constructed effectively from a given x. That is, there is a recursive function
f such that M’ = Mf(,). We note that if x E 1c then the computation of
Mfcx) on input y = 111 halts with 000 on its tape, and if x 4 K then the
computation of Mf(,) on input 111 never halts and its tape never contains
three consecutive 0’s. Cl
The transformations between Turing machines, partial recursive functions
and grammars as presented in Sections 4.5 and 4.8 can be used to obtain
undecidability results on grammars from undecidability results on Turing ma-
chines. We present a few simple examples.Example 5.42 Show that the following problems are undecidable:
(a) Given a grammar G and a string x, determine whether x E L(G).