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 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. 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 EMPTY_{TM}.)