Skip to main content
added 381 characters in body
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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.

added 978 characters in body
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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,

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$ is$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).

Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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.