Homework 10
Last updated: Mon, 21 Nov 2022 18:07:09 -0500
Out: Tue Nov 22, 00:00 EST Due: Mon Dec 05, 23:59 EST (2 weeks, due to Thanksgiving break)
This assignment explores mapping reducibility.
Homework Problems
Mapping Reducibility Step 2: If-and-only-if (5 + 6 = 11 points)
Re-Proving A_TM Undecidable (10 points)
No Mapping Red (10 points)
More If-and-only-if Practice (10 points)
README (1 point)
Total: 42 points
Submitting
Submit your solution to this assignment in Gradescope hw10. Please assign each page to the correct problem and make sure your solutions are legible.
A submission must also include a README containing the required information.
1 Mapping Reducibility Step 2: If-and-only-if
In class, we learned an alternate way to do undecidability proofs using mapping reducibility.
creating a computable function between the two languages, and
showing an if-and-only-if statement (which itself has two parts) holds for that computable function.
We then started to re-prove that some languages are undecidable using mapping reducibility. Specifically,
In class, to show EQ_{TM} undecidable, we showed that there is a computable function f mapping from E_\textsf{TM} to EQ_\textsf{TM}.
Complete the proof here.
Specifically,give the if-and-only-if statement that must be proved, and
show that the computable function that we created satisfies this if-and-only-if requirement. Don’t forget that proving an if-and-only-if statement requires two parts.
- Similarly, complete the proof of undecidability of \overline{E}_{TM} by:
giving the if-and-only-if statement that must be proved,
showing that the computable function from class satisfies this requirement, and
then showing that if \overline{E}_{TM} is undecidable, then E_{TM} is undecidable.
2 Re-Proving A_TM Undecidable
Prove (again) that A_\textsf{TM} is undecidable.
This time, however, you must reduce from the \textit{CS420}_\textsf{F22} language from the Trying To Decide About CS 420, Fall 2022 problem in Homework 9.
Also, you must use mapping reducibility.
Remember that mapping reducibility has two parts: a computable function, and an if-and-only-if statement (which itself has two parts).
Your answer must be a full proof of undecidability, i.e., the proof should conclude with something like "therefore A_{\textsf{TM}} is undecidable". In particular, mapping reducibility by itself is insufficient for proving undecidability
3 No Mapping Red
In problem Mapping Reducibility Step 2: If-and-only-if, it was mentioned that we showed there is a computable function mapping from A_\textsf{TM} to \overline{E}_\textsf{TM}. Explain why there cannot exist a mapping reduction from A_\textsf{TM} to E_\textsf{TM}?
4 More If-and-only-if Practice
Say that we are given some language L.
L is Turing-Recognizable if-and-only-if L is mapping reducible to A_\textsf{TM}