WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

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)}

     


Additional Problem for Students taking the course for Graduate Credit

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

Homework Submission