### CS4123 Theory of Computation  Homework 3 - B 2002

#### PROF. CAROLINA RUIZ

Due Date: Friday, November 22nd at 4:30 pm.
Help session: Thursday, November 21st at 3:00 pm. CS Annex

#### Problems

1. (20 points) Exercise 4.14 from textbook (page 170).

2. (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.

1. (10 points) Assume that the language L is decidable. Show that there is an enumerator E that enumerates L in length-increasing fashion.
2. (10 points) Assume that there is an enumerator E that enumerates L in length-increasing fashion. Show that the language L is decidable.

3. (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 LC 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.

4. (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 undecidable

USELESSTM,S = {<M, q> | where M is a Turing machine and q is a useless state in M}

5. (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:

NULLtm = {< M > | M is a TM and the empty string belongs to L(M)}