Given this language: $$L_{s_1,s_2} = \{ \langle M_1 \rangle \langle M_2 \rangle | L(M_1) \in S_1 \text{ and } L(M_2) \in S_2 \}$$ I want to prove that for $S_1=RE$ and $S_2=RE$, then $L_{S_1,S_2} \in R$.

The way I started was by trying to build a Turing Machine that decides $L_{S_1,S_2}$:

Let $M_{12}$ be that Turing machine.

  1. For each input word $w$:
  2. If $w$ cannot be decoded as $\langle M_1 \rangle \langle M_2 \rangle$ then halt and reject.
  3. Run $w$ on both $M_1$ and $M_2$.
  4. If one of the two machines above halted, then $M_{12}$ halts and accepts $w$.

And here I got stuck:

What if the two machines didn't stop over $w$? how should I halt and reject $w$ in $M_{12}$?


1 Answer 1


By definition, for every Turing machine $M$, $L(M) \in \mathsf{RE}$. Therefore your language can be rewritten as $$ \{ \langle M_1 \rangle \langle M_2 \rangle : M_1,M_2 \text{ Turing machines} \}. $$ This obviates some of the steps in your oddly named machine $M_{12}$.

  • $\begingroup$ there are machines where L(M)∈co-RE. but still, if you have an input that could be interpreted as $M_1$ and $M_2$ how can you check that the language of each machine is in $RE$? $\endgroup$ Dec 12, 2016 at 11:35
  • $\begingroup$ That fact that the language of some Turing machines belongs to coRE in no way contradicts the fact that the language of every Turing machine is in RE. $\endgroup$ Dec 12, 2016 at 11:37
  • $\begingroup$ i still don't understand why every TM $M$ the language it accepts (i.e. $L(M)$) must be in $RE$? Since there are languages which are not in $RE$, for instance $L_{EQ}=\{ <M_1><M_2>|L(M_1)=L(M_2) \}$ and the fact that there are some TM that accepts $L_{EQ}$, does not make $L_{EQ} \in RE$. $\endgroup$ Dec 12, 2016 at 12:37
  • 3
    $\begingroup$ The point is that there is no Turing machine that accepts $L_{EQ}$. However, RE is defined as the set of languages accepted (through halting) by Turing machines. $\endgroup$ Dec 12, 2016 at 13:22

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.