2012 May 1,

CS 254: Assignment K

Carleton College, Spring 2012

Prof. Joshua R. Davis, , Goodsell 106B, x4473

This assignment is due Friday at noon, as usual. You may not use Rice's theorem.

A. Do Exercise 5.4.

B. (This is the Turing machine version of a problem in program optimization: Given a program and a subroutine of that program, determine whether the subroutine is essential, or whether it can be optimized out.) Define ENTER_TM = {<M, q> : M is a Turing machine, q is a state of M, and there exists a string w such that M enters q while processing w}. Prove that ENTER_TM is undecidable.

C. (Recall that, for any two languages A and B, A / B = {w : there exists a string x in B such that wx is a string in A}. We have shown that if A is regular, then A / B is regular. That is, there must exist a DFA for A / B. Now we will prove that this DFA is not computable.) Prove that there does not exist a decider F that, given input <D, M>, where D is a DFA and M is a Turing machine, halts with a DFA C on its tape (and nothing else), such that L(C) = L(D) / L(M).

D. Do Problem 5.20.

E. Do Problem 5.33. (Disclaimer: I have not done it yet.)