Rice's theorem can be found in Hopcroft and Ullman (1979).
EXERCISES
1. Show in detail how the machine in Theorem 12.4 is constructed.
2. Show that the two problems mentioned at the end of the preceding section,
namely
(a) L (M) contains any string of length five,
(b) L (M) is regular,
are undecidable.
3. Let M 1 and M 2 be arbitrary Turing machines. Show that the problem “L(M 1 )
⊆ (M 2 ) ” is undecidable.
4. Let G be any unrestricted grammar. Does there exist an algorithm for
determining whether or not L(G) R is recursively enumerable?
5. Let G be any unrestricted grammar. Does there exist an algorithm for
determining whether or not L(G) = L(G) R ?
6. Let G 1 be any unrestricted grammar, and G 2 any regular grammar. Show that
the problem
L(G 1 ) L (G 2 ) = Ø
is undecidable.
7. Show that the question in Exercise 6 is undecidable for any fixed G 2 , as long
as L(G 2 ) is not empty.
8. For an unrestricted grammar G, show that the question “Is L(G) = L(G)*?” is
undecidable. Argue (a) from Rice's theorem and (b) from first principles.
12.3 The Post Correspondence Problem
The undecidability of the halting problem has many consequences of practical