2022 October 19,
Carleton College, Joshua R. Davis
A. Problem 4.20, which is about separating two languages. (Hint: .si egaugnal sti tahw tuoba kniht nehT .rediced a ngised tsriF)
B. Problem 5.15, which is about a Turing machine moving its head left. (Hint: .noisiced sti ekam neht dna sevom m rof tupni sti etalumis nac rediced ruoY .tupni sti morf ecuded nac rediced ruoy hcihw ,m rebmun a si erehT)
When a compiler compiles a program into machine language (or byte code), it usually performs optimizations to improve the speed or memory usage of the code. For example, the compiler may attempt to remove unnecessary code, that will never be called. Our final problem places a theoretical limit on that kind of optimization. Define ENTERTM to be the set of all strings <M, q>, where M is a Turing machine, q is a state of M, and there exists a string w such that M enters q while processing input w.
C. Prove that ENTERTM is undecidable.