# Why this Turing machine can't be an acceptor for the following language?

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 $$$$

1. In parallel simulate M1 on $$$$ and M2 on $$$$
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?

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

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.
• 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. Jun 26, 2020 at 16:54