# For $L_S=\{\langle M\rangle : L(M)\in S \}$ what know about $S$ if

For $$L_S=\{\langle M\rangle : L(M)\in S \}$$ what know about $$S$$ in case of:

1. $$L_S\in RE$$

2. $$L_S\in R$$

Rice's theorem states that if $$L_S$$ is not trivial (i.e., is not $$\varnothing$$ nor all languages) then $$L_S$$ can't be decided (it might be computationally enumerable, though).

An extension to Rice's theorem states that $$L_S$$ is computationally enumerable if and only if:

1. For all $$L_1, L_2$$ computationally enumerable, if $$L_1 \in L_S$$ and $$L_1 \subset L_2$$, then $$L_2 \in L_S$$.

2. If $$L \in L_S$$, there is a finite subset $$L' \subset L$$ so that $$L' \in L_S$$.

3. The set of finite languages in $$L_S$$ is computationally enumerable.

Proofs are given here.

Take a look at Rice's theorem and its extensions.

Basically, Rice's theorem and its extension state:

1. If $$\emptyset\neq S\subset RE$$ then $$L_S\notin R$$
2. If $$\emptyset \neq S\subset RE$$ and $$\Sigma^*\notin S$$ (please fix me if this is wrong, this is what I remember) then $$L_S\notin RE$$
• I believe this is a correct answer. Can you explain why the downvote? Maybe consider adding a comment so that I can fix the answer if it isn't correct. Jul 12 at 6:03