1
$\begingroup$

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.

Any suggestions please?

$\endgroup$

closed as unclear what you're asking by D.W., Nicholas Mancuso, lPlant, Shaull, Juho May 26 '15 at 7:14

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What have you tried? Why not use the course forum/email to ask questions (or get hints)? I'm sure the TAs would be glad to help... $\endgroup$ – Shaull May 25 '15 at 17:25
  • $\begingroup$ I think the system doesn't support lyx, hard to ask $\endgroup$ – Yotam May 25 '15 at 17:30
  • $\begingroup$ I still suggest email/forums. Anyway, you intuition seems right, how about showing reductions from $A_TM$ and $\overline{A_TM}$? $\endgroup$ – Shaull May 25 '15 at 17:33
  • $\begingroup$ Hint: show that if $L$ was semi-decidable, then all TM-languages would be decidable. $\endgroup$ – Raphael May 25 '15 at 18:29