3 added 381 characters in body edited Jan 2 '18 at 19:19 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges You missed a tiny detail when defining $$C$$: all those languages are RE by assumption; no other language can be an $$L(M)$$! Let us again look at the language you want to say something about: $$\qquad L = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \subseteq L\bigl(\, 0(0\cup1)^* \,\bigr) \}$$. We see that $$L \subseteq \Sigma^*$$ for some alphabet $$\Sigma$$ that depends on the TM encoding $$\langle \_ \rangle$$. Now recall the statement of Rice's theorem: the index set $$\qquad \Phi(X) = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \in X \}$$ of a language class $$X$$ is undecidable if $$\emptyset \subsetneq X \subsetneq \mathrm{RE}$$. Now, it is obvious (read: very easy to prove -- your exercise) that $$L = \Phi(C)$$ with $$\qquad C = \{ L \in \mathrm{RE} \mid L \subseteq L\bigl( 0(0+1)^* \bigr) \}$$$$\qquad C = \{ Y \in \mathrm{RE} \mid Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$$; the requirement $$\emptyset \subsetneq C \subsetneq \mathrm{RE}$$ is likewise trivial. We don't get to "just say" anything; we have to prove all three conditions -- $$L = \Phi(C)$$, $$\emptyset \subsetneq C$$, and $$C \subsetneq \mathrm{RE}$$ -- but is toit so happens that all three proofs are very easy here since $$L$$ has been defined in a very suitable way. For other languages, the proofs can be more intricate (or impossible; then Rice's theorem does not apply). Side note: If we consider $$\qquad C' = \{ Y \in \Sigma^* \mid Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$$ then we also get $$\Phi(C') = L$$! While there are non-RE $$X$$ in $$C'$$ (a simple if non-constructive argument is that there are uncountably many such $$X$$), $$\Phi$$ "ignores" them. However, $$C'$$ does not fulfill the conditions of Rice's theorem so we can not use it. You missed a tiny detail when defining $$C$$: all those languages are RE by assumption; no other language can be an $$L(M)$$! Let us again look at the language you want to say something about: $$\qquad L = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \subseteq L\bigl(\, 0(0\cup1)^* \,\bigr) \}$$. We see that $$L \subseteq \Sigma^*$$ for some alphabet $$\Sigma$$ that depends on the TM encoding $$\langle \_ \rangle$$. Now recall the statement of Rice's theorem: the index set $$\qquad \Phi(X) = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \in X \}$$ of a language class $$X$$ is undecidable if $$\emptyset \subsetneq X \subsetneq \mathrm{RE}$$. Now, it is obvious (read: very easy to prove -- your exercise) that $$L = \Phi(C)$$ with $$\qquad C = \{ L \in \mathrm{RE} \mid L \subseteq L\bigl( 0(0+1)^* \bigr) \}$$; the requirement $$\emptyset \subsetneq C \subsetneq \mathrm{RE}$$ is likewise trivial. We don't get to "just say" anything; we have to prove all three conditions -- $$L = \Phi(C)$$, $$\emptyset \subsetneq C$$, and $$C \subsetneq \mathrm{RE}$$ -- but is to happens that all three proofs are very easy here since $$L$$ has been defined in a very suitable way. For other languages, the proofs can be more intricate (or impossible; then Rice's theorem does not apply). You missed a tiny detail when defining $$C$$: all those languages are RE by assumption; no other language can be an $$L(M)$$! Let us again look at the language you want to say something about: $$\qquad L = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \subseteq L\bigl(\, 0(0\cup1)^* \,\bigr) \}$$. We see that $$L \subseteq \Sigma^*$$ for some alphabet $$\Sigma$$ that depends on the TM encoding $$\langle \_ \rangle$$. Now recall the statement of Rice's theorem: the index set $$\qquad \Phi(X) = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \in X \}$$ of a language class $$X$$ is undecidable if $$\emptyset \subsetneq X \subsetneq \mathrm{RE}$$. Now, it is obvious (read: very easy to prove -- your exercise) that $$L = \Phi(C)$$ with $$\qquad C = \{ Y \in \mathrm{RE} \mid Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$$; the requirement $$\emptyset \subsetneq C \subsetneq \mathrm{RE}$$ is likewise trivial. We don't get to "just say" anything; we have to prove all three conditions -- $$L = \Phi(C)$$, $$\emptyset \subsetneq C$$, and $$C \subsetneq \mathrm{RE}$$ -- but it so happens that all three proofs are very easy here since $$L$$ has been defined in a very suitable way. For other languages, the proofs can be more intricate (or impossible; then Rice's theorem does not apply). Side note: If we consider $$\qquad C' = \{ Y \in \Sigma^* \mid Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$$ then we also get $$\Phi(C') = L$$! While there are non-RE $$X$$ in $$C'$$ (a simple if non-constructive argument is that there are uncountably many such $$X$$), $$\Phi$$ "ignores" them. However, $$C'$$ does not fulfill the conditions of Rice's theorem so we can not use it. 2 added 978 characters in body edited Jan 2 '18 at 16:02 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges You missed a tiny detail when defining $$C$$: all those languages are RE by assumption; no other language can be an $$L(M)$$! In fact, $$L$$ is Let us again look at the language you want to say something about: $$\qquad L = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \subseteq L\bigl(\, 0(0\cup1)^* \,\bigr) \}$$. We see that $$L \subseteq \Sigma^*$$ for some alphabet $$\Sigma$$ that depends on the TM encoding $$\langle \_ \rangle$$. Now recall the statement of Rice's theorem: the index set $$\qquad \Phi(X) = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \in X \}$$ of a language class $$X$$ is undecidable if $$\emptyset \subsetneq X \subsetneq \mathrm{RE}$$. $$\qquad \{ L \in \mathrm{RE} \mid L \subseteq L\bigl( 0(0+1)^* \bigr) \}$$ Now, it is obvious (read: very easy to prove -- your exercise) that $$L = \Phi(C)$$ with which$$\qquad C = \{ L \in \mathrm{RE} \mid L \subseteq L\bigl( 0(0+1)^* \bigr) \}$$; the requirement $$\emptyset \subsetneq C \subsetneq \mathrm{RE}$$ is neither empty nor universallikewise trivial. We don't get to "just say" anything; we have to prove all three conditions -- $$L = \Phi(C)$$, so $$L$$$$\emptyset \subsetneq C$$, and $$C \subsetneq \mathrm{RE}$$ -- but is not decidable byto happens that all three proofs are very easy here since $$L$$ has been defined in a very suitable way. For other languages, the proofs can be more intricate (or impossible; then Rice's theorem does not apply). You missed a tiny detail when defining $$C$$: all those languages are RE by assumption; no other language can be an $$L(M)$$! In fact, $$L$$ is the index set of $$\qquad \{ L \in \mathrm{RE} \mid L \subseteq L\bigl( 0(0+1)^* \bigr) \}$$ which is neither empty nor universal, so $$L$$ is not decidable by Rice's theorem. You missed a tiny detail when defining $$C$$: all those languages are RE by assumption; no other language can be an $$L(M)$$! Let us again look at the language you want to say something about: $$\qquad L = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \subseteq L\bigl(\, 0(0\cup1)^* \,\bigr) \}$$. We see that $$L \subseteq \Sigma^*$$ for some alphabet $$\Sigma$$ that depends on the TM encoding $$\langle \_ \rangle$$. Now recall the statement of Rice's theorem: the index set $$\qquad \Phi(X) = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \in X \}$$ of a language class $$X$$ is undecidable if $$\emptyset \subsetneq X \subsetneq \mathrm{RE}$$. Now, it is obvious (read: very easy to prove -- your exercise) that $$L = \Phi(C)$$ with $$\qquad C = \{ L \in \mathrm{RE} \mid L \subseteq L\bigl( 0(0+1)^* \bigr) \}$$; the requirement $$\emptyset \subsetneq C \subsetneq \mathrm{RE}$$ is likewise trivial. We don't get to "just say" anything; we have to prove all three conditions -- $$L = \Phi(C)$$, $$\emptyset \subsetneq C$$, and $$C \subsetneq \mathrm{RE}$$ -- but is to happens that all three proofs are very easy here since $$L$$ has been defined in a very suitable way. For other languages, the proofs can be more intricate (or impossible; then Rice's theorem does not apply). 1 answered Dec 31 '17 at 18:39 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges You missed a tiny detail when defining $$C$$: all those languages are RE by assumption; no other language can be an $$L(M)$$! In fact, $$L$$ is the index set of $$\qquad \{ L \in \mathrm{RE} \mid L \subseteq L\bigl( 0(0+1)^* \bigr) \}$$ which is neither empty nor universal, so $$L$$ is not decidable by Rice's theorem.