# Is mapping reduction from $\overline{A_{TM}}$ possible?

I know $\overline{A_{TM}}$ is not Turing Recognizable (to prove it, infact, I proved its complement to be both Turing-recognizable and not decidable).

My question is, if $\overline{A_{TM}}$ is not Turing Recognizable, can I reduce $\overline{A_{TM}}$ to some language A (say $E_{TM}$) to show it is not Turing Recognizable, too? Or this does not makes sense, because it's not Turing Recognizable and so cannot exists such a reduction function/TM?

The notion of mapping reducibility is completely general:

Let $A, B \subseteq \Sigma^*$ be languages. $A \leq_{\mathrm{m}} B$ if there exists a computable function $f: \Sigma^* \rightarrow \Sigma^*$ such that

$$w \in A \iff f(w) \in B$$

No properties are required of $A$ or $B$.

We can use a mapping reduction from $\overline{A_{\mathsf{TM}}}$ to show that $EQ_{\mathsf{TM}}$ is not recognizable. Let $f$ be given by

$$f(\langle M,w \rangle) = \langle M', M'' \rangle$$

where $M'$ is the TM

"On input $x$ simulate $M$ on input $w$ and answer what $M$ answered"

and $M''$ is the TM that rejects every input.

Clearly, $M$ does not accept $w$ if and only if $L(M') = L(M'')$.

• Thank you. My doubt is on the fact that you're taking <M, w> as input to the f function, which is not recognizable, so to me this seems strange: how can I calculate something that is not Turing recognizable? If it's Turing recognizable, I know that on "yes" instances it will halt and answer "yes", but on instances "no" I'm not sure if it will halt, but what happens with non-Turing recognizable? – MoreOver Dec 10 '16 at 9:06
• The mapping reduction $f$ in my answer does not perform a secret test as to whether or not $M$ will accept $w$. Given a string $\langle M,w \rangle$, $f$ returns a string description of two Turing machines $M'$ and $M''$. $M'$ will simulate $M$ on input $w$ irrespective of the actual input. $M''$ will always reject. Neither of these machines will be constructed with knowledge of how $M$ behaves on input $w$. – Hans Hüttel Dec 10 '16 at 11:25
• And why this is not a problem? I mean, $M$ could not exists from what we know, or not? – MoreOver Dec 10 '16 at 12:30
• What do you mean by "$M$ could not exist"? The function $f$ is a function from the set of strings of the form $\langle M,w \rangle$ to strings of the form $\langle M',M''\rangle$, and I have provided a definition of it. $f$ must be defined so as to be a total function, and it is well-defined. Consider the function $g$ over the natural numbers defined by $$g(x) = x^2$$ Would you now say that it may not be possible to find the value $g(7)$, for we do not know if $7$ exists ? – Hans Hüttel Dec 10 '16 at 12:39
• Because I think $7$ ($w$) could be the description of a TM $M'$ and maybe $M$ does not know what to do on $<M'>$. If you know what to do for every $w$, then to me it seems $\overline{A_{TM}}$ is decidable (or recognizable at least). What happens in this case? We map "I don't know" to "I don't know"? I'm a bit confused on this. – MoreOver Dec 10 '16 at 12:51