Determine if for given some $L$, $S_L=\{\ L(M) | <M>\in L \}$ then for any $L$, if $S_L=RE$ then $L\in R$. Correct or Incorrect and explain why.

I think the claim is incorrect, and I'm trying to explain it with cardinals. I know that for each language we have $\aleph0$ turing machines and $|RE|$ is also $\aleph0$ but I know that is countable, actually, I don't know how to make the connection if $S_L=RE$ then is somehow is not counable.

Edit: I am looking to solve it with cardinals.


1 Answer 1


The statement is incorrect*. Consider that

$$ RE = \{L(M) \mid M \text{ is a turing machine} \} $$


$$\{ \langle M \rangle \mid M \text{ is a turing machine}\} \subseteq L \implies S_L =\{\ L(M) \mid \langle M \rangle \in L \} = RE$$

Therefore if I set

$$L = \{ \langle M \rangle \mid M \text{ is a turing machine}\} \cup \{ \#\langle M \rangle \mid M \text{ is a TM that always halts}\}$$

where # is some character that does not occur in turing machine encodings, we have $S_L = RE$ but $L \not\in R$ as the halting problem could be reduced to it.

* when assuming that $M$ in $S_L$ ranges over all turing machines. Otherwise the statement is ambiguous.

  • $\begingroup$ This is correct except for the incorrect statement that $S_L=RE\iff \{\langle M\rangle \mid M\text{ is a turing machine}\}\subseteq L$. Only one direction is correct, which is $\{\langle M\rangle \mid M\text{ is a turing machine}\}\subseteq L \implies S_L=RE$, which is the direction you actually use $\endgroup$
    – nir shahar
    Jul 28, 2021 at 11:30
  • $\begingroup$ @nirshahar Thanks for the hint. But can you actually come up with any $L$ for which the other direction actually doesn't hold? $\endgroup$
    – idmean
    Jul 28, 2021 at 11:36
  • $\begingroup$ Yes, for example $L_{M_0}:=\{\langle M\rangle \mid M \text{ is a TM}\} \setminus \{\langle M_0\rangle \}$ for any TM $M_0$ of your choice. Note that $\exists M: \langle M\rangle \in L \land L(M)=L(M_0)$ $\endgroup$
    – nir shahar
    Jul 28, 2021 at 11:39
  • $\begingroup$ @nirshahar Oh, of course, yes. Thanks, I wasn't thinking straight. $\endgroup$
    – idmean
    Jul 28, 2021 at 11:43
  • $\begingroup$ Thanks for this solution, But actually, I am trying to prove it with cardinal numbers reason, as I started to prove it to show that is not countable. $\endgroup$
    – John D
    Jul 28, 2021 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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