Assignment 10

In the following questions answering a “True or False” always requires providing a proof or a counter-example, as appropriate.

1. True or False: If \(A\leq_m B\) and \(B\) is co-Turing-recognizable, then \(A\) is also co-Turing-recognizable.
2. True or False: If \(A\leq_m B\) and \(A\) is decidable, then \(B\) is also decidable.
3. True or False: If \(A\leq_m B\) and \(A\) is Turing-recognizable, then \(B\) is also Turing-recognizable.
4. True or False: If \(A\leq_m B\), for some languages \(A\), \(B\), then we must also have \(B\leq_m A\).
5. Consider the language \(J\) consisting of all strings \(0w\) where \(w\in A_\textrm{TM}\) and \(1w\) where \(w\in \overline{A_\textrm{TM}}\).
   1. Show that \(A_\textrm{TM}\leq_m J\) and \(\overline{A_\textrm{TM}}\leq_m J\).
   2. Use this information to show that \(J\) is neither Turing-recognizable nor co-Turing-recognizable.
6. In this problem we address a number of questions related to having a language be mapping-reducible to its complement.
   1. Show that \(A_\textrm{DFA}\leq_m \overline{A_\textrm{DFA}}\).
   2. Show that if \(B\leq_m \bar{B}\), then \(B\) is Turing-recognizable if and only if it is co-Turing-recognizable.
   3. Show that if \(B\leq_m \bar{B}\) and \(B\) is undecidable, then \(B\) is neither Turing-recognizable nor co-Turing-recognizable.
   4. Give an example of an undecidable language \(B\) such that \(B\leq_m\bar{B}\).