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

  • $\begingroup$ 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? $\endgroup$
    – MoreOver
    Dec 10 '16 at 9:06
  • $\begingroup$ 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$. $\endgroup$ Dec 10 '16 at 11:25
  • $\begingroup$ And why this is not a problem? I mean, $M$ could not exists from what we know, or not? $\endgroup$
    – MoreOver
    Dec 10 '16 at 12:30
  • $\begingroup$ 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 ? $\endgroup$ Dec 10 '16 at 12:39
  • $\begingroup$ 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. $\endgroup$
    – MoreOver
    Dec 10 '16 at 12:51

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.