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.
- For each input word $w$:
- If $w$ cannot be decoded as $\langle M_1 \rangle \langle M_2 \rangle$ then halt and reject.
- Run $w$ on both $M_1$ and $M_2$.
- 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}$?