Given the following language - $L=\left\{\left\langle M_{1}, M_{2}\right\rangle \mid\left\langle M_{1}\right\rangle \notin L\left(M_{2}\right) \vee\left\langle M_{2}\right\rangle \notin L\left(M_{1}\right) \text { and are TM } M_{1}, M_{2}\right\}$

I know it's in CO-RE but why this is not a good acceptor for the above language?

On input $<M1,M2>$

  1. In parallel simulate M1 on $<M2>$ and M2 on $<M1>$
  2. if one rejects, accept.
  3. if both accept , reject.

according to definition of being acceptor of a language, for any input x that belongs to the language the acceptor accepts which it does it at phase 1. for any input which doesn't belongs to the language we either reject or not halt which is also the case.

what am i missing?

  • $\begingroup$ How do you check whether a word is in the language of the second machine, and when will you know the result? $\endgroup$
    – greybeard
    Jun 27, 2020 at 4:13

1 Answer 1


You are not considering the fact that $M_1(M_2)$ and/or $M_2(M_1)$ might not halt. When this happens your Turing machine for $L$ will be stuck executing step 1.

  • $\begingroup$ mmm... if they both don't halt then they are supposed to being accepted am I right? and then there is a yes instance which we didn't accept...? $\endgroup$
    – user314124
    Jun 26, 2020 at 16:53
  • $\begingroup$ That's correct. If both $M_1(M_2)$ and $M_2(M_1)$ do not halt then your TM should accept but it does not. The same happens if one of $M_1(M_2)$ and $M_2(M_1)$ accepts and the other does not halt. This of course is not a proof that $L$ is not in RE. $\endgroup$
    – Steven
    Jun 26, 2020 at 16:54
  • $\begingroup$ Very clear! thanks $\endgroup$
    – user314124
    Jun 26, 2020 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.