0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ regarding the second quote, I didn't state the correct one, sorry. I now edited the post. $\endgroup$ – younes zeboudj Jan 30 at 11:20
  • $\begingroup$ @youneszeboudj I edited the answer. $\endgroup$ – Bader Abu Radi Jan 31 at 10:26

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.