World's most popular travel blog for travel bloggers.

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

, , No Comments
Problem Detail: 

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?

Asked By : MoreOver
Answered By : Hans Hüttel

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'')$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback