[4 points] Exercise 9.2.4 in the text.

[6 points] Show that the recursive languages are closed under

union and

intersection.

[4 points] Prove that the following question is undecidable (i.e., prove that the corresponding language is not recursive): Given a Turing Machine M and a state q of M, is there any input that will cause M to enter state q? [This problem is analogous to the problem of finding

*dead code*in, say, a Java program: Given a Java program and a block of code within that program, is there some input that will cause that block of code to be executed?][4 points] Prove that the following question is undecidable: Given two Turing Machines, do they accept the same language? [This problem is analogous to the problem of determining if two Java programs are equivalent.]