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.


1 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.

  • $\begingroup$ Okay, in my example there exists a function with the set of all languages which have this property. Every Typ-0 language has the empty language as a subset, so it has to be trivial. Does it just mean that we cannot apply the theorem and therefore I have to show with a reduction that it's not decidable? I think there must be a relation between the language L and the language $L_1(M)=$$\emptyset$ which is undecidable. $\endgroup$ Aug 31, 2019 at 21:45
  • $\begingroup$ @BreadCrust, that is quite a different question (if I understand you correctly), Please post it as such (give details of your "function on the languages" and so on). $\endgroup$
    – vonbrand
    Sep 24, 2019 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.