# Turing machine decides languages in RE

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

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}$.
• 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$? Dec 12, 2016 at 11:35
• 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$. Dec 12, 2016 at 12:37
• 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. Dec 12, 2016 at 13:22