Rice Theorem - Problem to understand and apply it

Question

I have struggle to understand the Rice Theorem.

My understanding of Rice Theorem:

The purpose of this Theorem is to proof that some given language L is undecidable iff the language has a non-trivial propertie.

So, if I want to apply this Theorem I have to show that the following conditions are satisfied:

1) There are two TM's which have the same language and they are either both in the language $L(M_1)=L(M_2)$ or neither is in L ($M_1 \wedge M_2$ are no specific (picked) machines).

2) I have to show that there exists two specific TM's: $M_1'$ which has the property and $M_2'$ which doesn't have the property.

Is this correct?

Perhaps someone can give an example, so that I know how to apply the rice theorem.

What's about the language: $L=${$<M>$|$\emptyset$ $\subseteq$ $L(M)$}

For the first condition:

There are two turing-machine's which have the same language and doesn't accept the language L.

For the second condition:

• $M_1$ is the turing-machine that accepts all, and...
• $M_2$ is the turing-machine that rejects all.

So both conditions are true which implies I can apply the Rice Theorem?

Thank's for your help.

Answer 1

From Wikipedia:

Let S be a set of languages that is nontrivial, meaning

1. there exists a Turing machine that recognizes a language in S,
2. there exists a Turing machine that recognizes a language not in S.

Then it is undecidable to determine whether the language recognized by an arbitrary Turing machine lies in S.

It's the language (determined by the TM) that has the property, not the TM itself. Your first condition is not needed at all, and the second condition should state "$L(M_1')$ has the property, and $L(M_2')$ does not."

An example of application of Rice's Theorem might be the following statement. The set $$S = \{<M> : \varepsilon \in L(M)\}$$ is undecidable. The corresponding TMs might be $M_1$ which only accepts $\varepsilon$ and $M_2$ which doesn't accept any words.

Your example is not correct since the property is trivial. $\emptyset \subseteq A$ for any set $A$, even an empty set.