patternMinor
Is mapping reduction from $\overline{A_{TM}}$ possible?
Viewed 0 times
overlinepossiblereductionmappingfrom
Problem
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?
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?
Solution
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'')$.
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'')$.
Context
StackExchange Computer Science Q#67171, answer score: 5
Revisions (0)
No revisions yet.