Homework 11

CS 3810 – Summer 2008

1. [4 points] Exercise 9.2.4 in the text.

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

   1. union and

   2. intersection.

3. [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. [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.]