I was asked to prove that the language {(M1),(M2)|M2 accepts (M1) , and M1 doesn't accept (M2)} isn't in RE, and not in co-RE.
I tried reductions but didn't seem one that works, I also tried variations of the proof that Ld isn't in RE, but didn't managed that either.
Any one has an idea how to prove that?
Thanks in advance :)
We show reduction from $HP$ and $\overline{HP}$
$$ f(<M>,x) = <M_{\phi}>, <M_{x}>$$
$M_{x}$ on input $w$ will act as follows:
$M_{\phi}$ just rejects every input word right away (so it's language is empty).
Now observe that if $M$ halts on $x$, then $L(M_{x})=\Sigma^{*}$ and otherwise it accepts the empty language too, so correctness follows.
The reduction from $\overline{HP}$ would be: $$ f(<M>,x) = <M_{x}>, <M_{\Sigma^{*}}>$$
$M_x$ as before, and $M_{\Sigma^{*}}$ accepts every input word right away.
correctness follows again from the same observation.