5.6 Undecidable Problems
Exercises 5.6
277
1. For each of the following problems about Turing machines, determine
whether it is decidable or not:( a Given a one-way, one-tape DTM IU (defined in Section 4.1) and
a string x, determine whether the tape head of IV will ever visit
the (2n)th cell in the computation of AI on input x, where n = 1x1
(we call the leftmost cell of the tape the 0th cell, and the one to
its right the first cell, etc.).
Given a two-way, one-tape DTM AI (defined in Section 4.3) and
a string x, determine whether the tape head of IV will ever visit
the (2n)th cell in the computation of AI on input x, where n = ]zI
(we call the cell holding the leftmost symbol of II: the first cell, and
the cell to its right the second cell, etc.).
(c) Given a two-way, one-tape DTM AI and a string x, determine
whether the tape head of AI will move left for more than n times
(not necessarily in consecutive moves) in the computation of A&
on input 1x3, where n = 1~1.
(d) Given a two-way, one-tape DTM AI whose tape symbol set is
I’ = {a, b, B} and a string 2 E {a, b}*, determine whether M will
ever overwrite a symbol a by a symbol b in its computation on
input x.
(e) Given two DTM’s l& and Mz and two strings x1 and ~2, deter-
mine whether it is true that sometime during the computation of
AI1 on input xl and the computation of A& on input ~2, the first
three cells of their tapes contain the same symbols (i.e., whether
there is a configuration cx of the computation of A&(x1) and a
configuration ,0 of the computation of A&(Q) such that the first
three tape symbols of a is the same as those of p>.- For each of the following problems about unrestricted grammars, deter-
mine whether it is decidable or not:
( a
(b) Given a grammar G over the alphabet {a, b, c}, determine whether
L(G) contains a string x of which aau occurs as a substring.
) Given a grammar G and a string ;x: E L(G), determine whether
there is a derivation of x that does not contain a sentential form
in which UAU occurs as a substring, where a is a terminal symbol
and A is a nonterminal symbol in G.
(c) Given a grammar G and a string 2 E L(G), determine whether
there is a derivation of x in which the lengths of the sentential
forms do not decrease.
(d) Given a grammar G and a string IX: E L(G), determine whether
there is a derivation of IX: in which the lengths of the sentential
forms decrease at most n times, where n = lx].