Some Confusing Terms
Language Decided
We say a TM decide a language $L$ if it accepts all strings in $L$ and rejects all strings not in $L$. (Here, the TM should not accept any string not in $L$, but when we say a TM accept a word $w$, it may accept any other word also)
Language Recognized
We say a TM recognizes language L if it accepts all strings in L. It may or may not reject any string not in L- i.e., it might go into an infinite loop in case of non-acceptance. (It will never accept a string not in L)
Please go through the below videos first, then the given examples and for more examples see the reference link
Rice’s Theorem
Part 1 (For some undecidable languages)
Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable
For a property of recursively enumerable set to be non-trivial, there should exist at least recursively enumerable languages, (hence two Turing machines), the property holding for one ($T_{yes}$ being its TM) and not holding for the other ($T_{no}$ being its TM).
Thus, as per Rice’s theorem the language describing any nontrivial property of Turing machine is not recursive. It can either be recursively enumerable or not recursively enumerable. (Obviously there are also other languages which are not recursive).
PS: Any “trivial” property is always decidable – because the decision is known ahead and that is why the property is trivial.
Examples
(1) $L(M)$ has at least 10 strings
We can have $T_{yes}$ for $\Sigma^*$ and $T_{no}$ for $\phi$. Hence, $L = \left\{M \mid L(M) \text{ has at least 10 strings}\right\}$ is not Turing decidable (not recursive). (Any other $T_{yes}$ and $T_{no}$ would also do. $T_{yes}$ can be any TM which accepts at least 10 strings and $T_{no}$ any TM which doesn’t accept at least 10 strings )
(2) $L(M)$ has at most 10 strings
We can have $T_{yes}$ for $\phi$ and $T_{no}$ for $\Sigma^*$. Hence, $L = \{M\mid L(M)$ has at most 10 strings$\}$ is not Turing decidable (not recursive).
(3) $L(M)$ is recognized by a $TM$ having even number of states
This is a trivial property because for any r.e. language we have a TM and even if that TM is having odd number of states we can make an equivalent TM having even number of states by adding one extra state. Thus this set equals the set of recursively enumerable languages and hence decidable.
(4) $L(M)$ is a subset of $\Sigma^{*}$
This is a trivial property. All languages are subset of $\Sigma^{*}$ and hence this set contains all languages including all recursively enumerable languages.
Part 2 (For some unrecognizable language)
Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable
For a property of recursively enumerable set to be non-monotonic, there should exist at least two recursively enumerable languages (hence two Turing machines), the property holding for one ($T_{yes}$ being its TM) and not holding for the other ($T_{no}$ being its TM) and the property holding set (language of $T_{yes}$) must be a proper subset of the set not having the property (language of $T_{no}$).
Examples
(1) $L(M)$ is finite
We can have $T_{yes}$ for $\phi$ and $T_{no}$ for $\Sigma^*$ ($\phi \subset \Sigma^*$). Hence, $L = \{M\mid L(M)$ is finite$\}$ is not Turing recognizable (not recursively enumerable)
(2) $L(M) = \{0\}$
We can have $T_{yes}$ for $\{0\}$ and $T_{no}$ for $\Sigma^*$ ($\{0\} \subset \Sigma^*$). Hence, $L = \{M\mid L(M) = \{0\}\}$ is not Turing recognizable (not recursively enumerable)
(3) $L(M)$ is regular
We can have $T_{yes}$ for $\phi$ and $T_{no}$ for any non-regular language. Hence, $L = \{M\mid L(M)$ is regular$\}$ is not Turing recognizable (not recursively enumerable)
(4) $L(M)$ is not regular
We can have $T_{yes}$ for $\{a^nb^n\mid n\ge0\}$ and $T_{no}$ for $\Sigma^*$ ($\{a^nb^n\mid n\ge0\}\subset \Sigma^*$). Hence, $L = \{M\mid L(M)$ is not regular$\}$ is not Turing recognizable (not recursively enumerable)
(5) $L(M)$ is infinite
We cannot have $T_{yes}$ and $T_{no}$ such that $L(T_{yes}) \subset L(T_{no})$. Hence, this is not a non-monotonic property and Rice’s $2^{nd}$ theorem is not applicable. Still, $L = \{M\mid L(M)$ is infinite $\}$ is not Turing recognizable (not recursively enumerable)
(6) $L(M)$ has at least 10 strings
We cannot have $T_{yes}$ and $T_{no}$ such that $L(T_{yes}) \subset L(T_{no})$. Hence, this is not a non-monotonic property and Rice’s $2^{nd}$ theorem is not applicable.
This language is in fact Turing recognizable. See here
(7) $L(M)$ has at most 10 strings
We can have $T_{yes}$ for $\phi$ and $T_{no}$ for $\Sigma^*$($\phi \subset \Sigma^*$). Hence, $L = \{M\mid L(M)$ has at most 10 strings$\}$ is not Turing recognizable (not recursively enumerable)
Reference
More Examples can be seen here
