2013 May 9,
Carleton College, Spring 2013
Prof. Joshua R. Davis, , CMC 325, x4473
A. Problem 5.20. (Hint: Do a non-constructive proof.)
In programming languages, when a compiler compiles a program into machine language (or byte code, or any other intermediate form), it usually performs optimizations, to improve the speed or memory footprint of the code. For example, the compiler may attempt to remove unnecessary code. This next problem places a theoretical limit on that particular optimization.
B. Define ENTERTM = {<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 ENTERTM is undecidable.
C. Problem 5.9. Do not use Rice's theorem.
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}. In an earlier assignment, we showed that if A is regular, then A / B is regular. Our proof was non-constructive. This next problem suggests that the proof must be non-constructive.
D. Prove that there does not exist a Turing machine N 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). Notice that N must halt on all inputs, but we do not care whether it accepts or rejects them. (Hint: Use N to build a decider for EMPTYTM.)