Homework 3 - B 2002

**(20 points)**Exercise 4.14 from textbook (page 170).**(20 points)**Let Sigma be an alphabet. Prove that a language L over Sigma is decidable if and only if there is a TM E that enumerates L in such a way that the strings in L are output by E in length-increasing fashion. That is, prove the following two statements.- (10 points) Assume that the language L is decidable. Show that there is an enumerator E that enumerates L in length-increasing fashion.
- (10 points) Assume that there is an enumerator E that enumerates L in length-increasing fashion. Show that the language L is decidable.

**(20 points)**Prove that the set of semi-decidable languages is not closed under complementation. That is, PROVE that there is at least one semi-decidable language L whose complement L^{C}is not semi-decidable.

**Hint:**Read in detail the proof of Theorem 4.16 (p. 167) first and then use this Theorem to prove that there must be semi-decidable languages whose complements are not semi-decidable.**(20 points)**Exercise 5.13 from textbook (page 195).**Hint:**Prove first that the following problem is undecidable: Given a Turing machine M and a state q in M, determine whether or not q is a useless state. That is, prove that the following language is undecidableUSELESS

_{TM,S}= {<M, q> | where M is a Turing machine and q is a useless state in M}**(20 points)**Prove that determining if a Turing machine accepts the null/empty string is undecidable. That is, prove that the following language is undecidable:NULL _{tm}= {< M > | M is a TM and the empty string belongs to L(M)}

**(10 points)**Problem 5.22 from textbook (Rice's Theorem).

- by handing in your solutions during class on Friday, November 22nd.
- by handing in your solutions during Beth's office hour on Friday, November 22st, 10am - 11am.
- by leaving your solutions in my mailbox (CS office FL233). PLEASE MAKE SURE YOU LEAVE YOUR SOLUTIONS IN **MY** MAILBOX (the one UNDER the arrow marked with my lastname RUIZ).

You can submit this homework assignment in any of the following ways. Make sure you hand it in BY 4:30 pm on Friday, November 22nd.