Mapping Reductions to Complement of A$_{TM}$

Question

I have a general question about mapping reductions. I have seen several examples of reducing functions to $A_{TM}$

where $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine which accepts string } w\}$

which is great for proving undecidability. But say I want to prove unrecognizability instead. That is, I want to use the corollary that given $A \le_{m} B$, if $A$ is unrecognizable then $B$ is unrecognizable.

So for any arbitrary unrecognizable language $C$ which can be reduced to $\overline{A_{TM}}$ (any example language would suffice for sake of example), how can I reduce $\overline{A_{TM}} \le_{m} C$?

For simplicity, suffice to merely consider TM in $\overline{A_{TM}}$.

EDIT

For clarification, $\overline{A_{TM}} = \{ \langle M, w \rangle : M \text{ is a turing machine which does not accept string } w \}$

Answer 1

Let's take $L_{\emptyset}=\{ \langle M \rangle \mid L(M) = \emptyset \}$, that is, all the machines that accept no word (i.e., whose language is empty).

Now we show the reduction $\overline{A_{TM}} \le L_\emptyset$. The reduction is done by taking an input $(\langle M \rangle,w)$ of $\overline{A_{TM}}$ and converting it into an input ${\langle \tilde M \rangle}$ for $L_\emptyset$ such that

$$(\langle M \rangle,w) \in \overline{A_{TM}} \quad\text{ iff }\quad \langle \tilde M \rangle \in L_{\emptyset}$$

Given $(\langle M \rangle,w)$ we can construct $\tilde M$ in th following way. $\tilde M$ on input y does the following:

1. deletes the tape
2. writes $w$ on the tape
3. runs $M$ on $w$, and performs the same (if $M$ accepts, $\tilde M$ accepts as well).

Convince yourself it is possible to construct the coding of $\tilde M$ from the coding of $M$ and from $w$. Now let's verify that this reduction is valid:

• If $(\langle M \rangle,w) \in \overline{A_{TM}}$ then $M$ either rejects or doesn't halt. If so, then also $\tilde M$ doesn't accept $y$, for any input $y$. This means $L(\tilde M) = \emptyset$ thus $\langle \tilde M \rangle \in L_{\emptyset}$.
• If $(\langle M \rangle,w) \notin \overline{A_{TM}}$ then $M$ accepts $w$, thus $\tilde M$ accepts $y$ (for every $y$). It follows that $L(\tilde M)=\Sigma^*$ which implies that $\langle \tilde M \rangle \notin L_{\emptyset}$.

The "iff" condition holds and we successfully mapped an input of $\overline{A_{TM}}$ into an input of $L_\emptyset$. In this case we say we reduced $\overline{A_{TM}}$ to $L_\emptyset$. That is, if we can solve $L_\emptyset$, we can also solve $\overline{A_{TM}}$ by first converting the input and then running the algorithm that solves $L_\emptyset$ on the converted input.

Answer 2

You cannot show, for an arbitrary unrecognizable language $C$, that $\overline{A_{TM}} \leq_m C$. If $\overline{A_{TM}} \leq_m C$ then in particular the Turing degree of $C$ is greater than or equal to the Turing degree of $\overline{A_{TM}}$, because many-one reducibility implies Turing reducibility. The Turing degree of $\overline{A_{TM}}$ is $0'$, the same as the Turing degree of $A_{TM}$. There are plenty of unrecognizable languages whose Turing degree is incomparable with $0'$ (neither greater nor less than $0'$).

The example that Ran G. gave works because $L_\emptyset$ in particular is $m$-equivalent to $\overline{A_{TM}}$. There is a general phenomenon that most "natural" problems tend to be comparable with each other in $m$-degree. But if you look at arbitrary problems this is no longer true.