# 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

## 1 Answer

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