1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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$ Commented 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$ Commented 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$ Commented 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$ Commented Dec 12, 2016 at 13:22

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.