1
$\begingroup$

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

  1. $L_S\in RE$

  2. $L_S\in R$

$\endgroup$

2 Answers 2

1
$\begingroup$

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 computably enumerable, though).

An extension to Rice's theorem states that $L_S$ is computably enumerable if and only if after replacing $S$ with $S\cap RE$, all the following hold.

  1. For all $L_1, L_2$ computably enumerable, if $L_1 \in S$ and $L_1 \subseteq L_2$, then $L_2 \in S$.

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

  3. The set of finite languages in $S$ is computably enumerable.

Proofs are given at here.

$\endgroup$
-1
$\begingroup$

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$
$\endgroup$
1
  • 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
    Commented Jul 12, 2021 at 6:03

Your Answer

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

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