Answer Happy

Problem 7:[25 points] [Undecidability and Reductions] OVERLAPPING = {(M, D): | M is a Turing Machine and D is a DFA such that L(M) n L(D) 0}. That is, there exists at least one string w € L(D) such that M halts on w and accepts it. 1. Show that OVERLAPPING is undecidable using reductions. You can reduce ATM or ETM or any of the undecidable languages that was discussed in class, homework, or practice problems. [7 points]
2. Show that OVERLAPPING is Turing recognizable. That is, give a Turing machine that halts and accepts (M, D) when (M, D) E OVERLAPPING. [8 points]
3. Given a language L₁ C (0U1)*, let L₂ = {0w w€ L₁}U {1v | v ¢ L1}. (a) Prove that L1 ≤m L₂ (reduce L₁ to L₂). (b) Prove that L₁ ≤m L2. (c) If L₁ is undecidable, then what can you infer about L₂? [4 points] [4 points] [2 points]