0
$\begingroup$

I read some computation theory lecture notes and after citing and proving the proposition: $\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$ it says that $\emptyset\in S$ is not a sufficient condition, i.e $L_S \notin RE$ doesn't yield $\emptyset \in S$, by giving the counter example $L_{\Sigma ^*}:= \{\langle M\rangle : L(M) = \Sigma^*\}\notin RE$ . However it says that there is a necessary and sufficient condition under which $L_S\notin RE$. I searched in Sipser's book for this condition but couldn't find it. I would really appreciate a reference for this condition.

Edit : given the answer by @dkaeae , I wish to know what is the stronger property one can deduce about a non-trivial $S\subset RE$ in case $L_S \notin RE$.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ It seems that you mean $\emptyset\in S$ is not a necessary condition from your contexts. $\endgroup$ – xskxzr Aug 19 '19 at 12:24
  • $\begingroup$ Added the definition of $L_{\Sigma^*}$. I thought I had a counter example for cases in which $\emptyset \notin S$ and $L_S \in RE$ and thus $\emptyset \in S$ is a necessary condition, but it seems I have a problem with this counter examples so I have to rethink. $\endgroup$ – dan Aug 19 '19 at 14:56
  • $\begingroup$ The condition $\emptyset\in S$ cannot derive $L_S\notin \mathrm{RE}$. For example, if $S$ is the set of all languages, to which $\emptyset$ belongs certainly, then $L_S$ is the set of descriptions of all TMs, which certainly belongs to RE. $\endgroup$ – xskxzr Aug 20 '19 at 2:39
  • $\begingroup$ I deleted my answer because evidently I completely messed up decidable and RE... (It happens.) $\endgroup$ – dkaeae Aug 22 '19 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.