Page 1 of 1
Problem 7 : [25 points) (Undecidability and Reductions] OVERLAPPING = {(M, D): | M is a Turing Machine and D is a DFA su
Posted: Mon May 09, 2022 5:54 am
by answerhappygod
- 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 25 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)