1
$\begingroup$

Consider language $L = \{<M> |L(M) \subseteq L(0(0\cup1)^*) \}$ where $<M>$ is a valid encoding of a turing machine.

I know that the language is applicable for Rice Theorem. Now, I understand that in this case the language group in $RE$ is:

$C = \{L\subseteq \Sigma^*|L\subseteq L(0(0\cup1)^*)\}$

However, I'm not sure how to prove that each of these languages is in the $RE$ class. Note That an alphabet wasn't given in the exercise so I guess that there can be other letters. I thought at first it had something to do with the languages being subests of a regular language, but then again $\Sigma^*$ is a regular language and all other languages are its subsets.

$\endgroup$
  • 1
    $\begingroup$ $L\in \Sigma^*$ means that $L$ is a word, not a language. You probably mean $L\subseteq \Sigma^*$. $\endgroup$ – chi Dec 31 '17 at 17:29
  • 1
    $\begingroup$ Also note that the sub-languages $L$ of $0(0\cup 1)^*$ are uncountably many, so surely some of them are not RE. I think you are not applying Rice correctly -- you probably should consider the recognizable sub-languages, only. $\endgroup$ – chi Dec 31 '17 at 17:31
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think I get it now from your answer and Chi's comment. You can say that this language is equal to the language with C as the enumerable subsets of the given set because if you remove the un-enumerable subsets it does't affect any other TM's in the set (doesn't exclude them) so the sets are equal. $\endgroup$ – Eloo Jan 2 '18 at 18:40
  • $\begingroup$ @Eloo I have no idea what you're getting at there; I think you're making things more complicated than they are. But if it makes sense to you now, great. $\endgroup$ – Raphael Jan 2 '18 at 19:12

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.