Problem Detail: 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 }$
Asked By : RageD
Answered By : Ran G.
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}} quadtext{ 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:
- deletes the tape
- writes $w$ on the tape
- 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1603
