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

  • $\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$ – ThunderWiring Dec 12 '16 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$ – Yuval Filmus Dec 12 '16 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$ – ThunderWiring Dec 12 '16 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$ – Yuval Filmus Dec 12 '16 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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