- Problem 7 25 Points Undecidability And Reductions Overlapping M D M Is A Turing Machine And D Is A Dfa Su 1 (34.91 KiB) Viewed 22 times
- Problem 7 25 Points Undecidability And Reductions Overlapping M D M Is A Turing Machine And D Is A Dfa Su 2 (13.85 KiB) Viewed 22 times
- Problem 7 25 Points Undecidability And Reductions Overlapping M D M Is A Turing Machine And D Is A Dfa Su 3 (23.74 KiB) Viewed 22 times
Problem 7 : [25 points) (Undecidability and Reductions] OVERLAPPING = {(M, D): | M is a Turing Machine and D is a DFA such that L(M) L(D) 70 }. That is, there exists at least one string w E L(D) such that M halts on w and accepts it. 1. Show that OVERLAPPING is undecidable using reductions. You can reduce Atm or Erm 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, SOU 1)*, let L2 {OW | W € Li} U{lv | V&L1}. (a) Prove that Li <m L2 (reduce L, to L2). [4 points] (b) Prove that I <m L2. [4 points] (C) If L1 is undecidable, then what can you infer about L ? [2 points)