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$
  • 1
    $\begingroup$ 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. $\endgroup$
    – nir shahar
    Jul 12 at 6:03

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.