# Proving that pairs of words in resp. not in a TMs language are neither semi- nor co-semi-decidable [closed]

I have a homework assignment in which I am required to determine if $$L = \{ \langle M,x,y \rangle : x\in L(M),y\notin L(M) \}$$ is in $$R,RE-R,coRE-R \text{ or } \overline{RE \cup coRE}$$

Now, my instinct tells me that $L_1 \in \overline{RE \cup coRE}$, because how can you show that a machine $M$ does not recognize a string $y$? However, I don't know how to prove it. The only such language I know is $$EQ_{TM} = \{ \langle M_1,M_2 \rangle : L(M_1)=L(M_2)\}$$ and I don't see a reduction from the latter to the former.

• I still suggest email/forums. Anyway, you intuition seems right, how about showing reductions from $A_TM$ and $\overline{A_TM}$? – Shaull May 25 '15 at 17:33
• Hint: show that if $L$ was semi-decidable, then all TM-languages would be decidable. – Raphael May 25 '15 at 18:29