1. Prove that the language L = fhMi j M when started on the blank tape, eventually writes a $ somewhere on the tapeg is undecidable. Use the undecidability of ATM to do this. 2. Give a reduction from HALTTM = fhM; wi j M is a TM which halts on wg to L = fhM; ji j M halts on all inputs with less than j 1’sg: Prove it’s a reduction. 3. Show that ETM is recognizable by giving a high level description of a nondeterministic TM which recognizes it. 4. Show that fhM1; M2i j L(M1) \ L(M2) = ;g is not recognizable. Use ETM. 5. Say a TM M is reversible if for every string w, M accepts w iff M accepts the reverse of w. (Recall that the reverse of w1w2 : : : wk is wkwk−1 : : : w1.) Prove that the language T = fhMi j M is a reversible TMg is undecidable. 1
