7
$\begingroup$

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 \}$

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I apologize, my wording was poor. I meant an arbitrarily specific problem which is unrecognizable. I was merely looking for an example to better understand the reductions. $\endgroup$ – RageD May 3 '12 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.