# EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?

So as I understand $$EQ_{TM}$$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $$A_{TM}$$ is reducible to its complement $${NEQ_{TM}}$$). But we can also reduce $$A_{TM}$$ to $$EQ_{TM}$$ itself, that means: $$EQ_{TM}$$ and $${NEQ_{TM}}$$ are not disjoint since we can reduce $$A_{TM}$$ to the two of them? And also, $$EQ_{TM}$$ is not Turing recognizable but it contains some instance that is turing recognizable since we can reduce $$A_{TM}$$ to it?

I have an intuition that these two questions have 'YES' as an answer and they are not problematic: it is OK to answer them with YES. But I have an unclear image about the fact of being a complement but having some shared elements with its complement, maybe the elements that are shared are just the strings but not the problems themselves?

Any clarifications would be welcome

Note that $$EQ_{TM}$$ is the language of machines that recognize the same language (they are not necessarily equivalent).

You said

But we can also reduce $$A_{TM}$$ to $$EQ_{TM}$$ itself, that means: $$EQ_{TM}$$ and $$NEQ_{TM}$$ are not disjoint since we can reduce $$A_{TM}$$ to the two of them?

This is far from being true, if there are reductions from a language $$A$$ to two languages $$B$$ and $$C$$, this does not say anything about $$B\cap C$$ as the reductions need not be related. To be concrete, it is shown here that every non-trivial language is $$\text{R}$$-hard, so clearly, you cannot claim that every two non-trivial languages intersect.

You also said

And also, $$EQ_{TM}$$ is not Turing recognizable but it contains some instance that is turing recognizable since we can reduce $$A_{TM}$$ to it?

Clearly, $$EQ_{TM}$$ contains some instances $$\langle M_1, M_2 \rangle$$, where it is easy to check whether $$L(M_1) = L(M_2)$$ (for example, all instances where $$M_2$$ is identical to $$M_1$$ with some new unreachable states). Also, you're right, this indeed can be thought of a consequence of the existence of a reduction from $$A_{TM}$$ to $$EQ_{TM}$$. Formally, we have the following claim (I leave it to you as a good non-trivial exercise), and thus the image of the reduction (which is a subset of $$EQ_{TM}$$) is in $$\text{RE}$$.

Claim: Let $$f: \Sigma^* \to \Sigma^*$$ be a computable function and let $$L\subseteq \Sigma^*$$ be a language in $$\text{RE}$$. It holds that $$f(L) = \{ f(x): x\in L \}\in \text{RE}$$.

BTW, complement languages, by definition, have empty intersection. So, regarding the question in the title, you can reduce $$A_{TM}$$ to $$EQ_{TM}$$ (here is a hint: there they asked about a reduction from the halting problem, but the hint is also good for your case), and being able to define such a reduction does not contradict anything.

• regarding the second quote, I didn't state the correct one, sorry. I now edited the post. Jan 30, 2021 at 11:20
• @youneszeboudj I edited the answer. Jan 31, 2021 at 10:26