Rice's Theorem and Decidability

Learn about Rice's theorem and how to use it in proving the undecidability of certain problems.

Rice’s theorem

Any nontrivial property of recursively enumerable languages is undecidable.

It is the fact that we have looked for algorithms—which by definition are Turing machines that always halt—to determine properties of computations that may not halt that has led to so many undecidable results. A “property” of languages equates to a set of languages (i.e., the languages that have that property). By “trivial,” we mean properties that are either obviously always false for every RE language, or always true for every RE language. For example, we know that the problem EE, which determines if an arbitrary language has the property of “emptiness,” is undecidable. We could have concluded this directly from Rice’s theorem, however, because some languages are empty and some are not. This is what is meant as a “nontrivial” property—one that holds for some TM\text{TM}s and not for others. All the reductions involving nontrivial properties of TM\text{TM}s are undecidable.

It is important to understand that Rice’s theorem only applies to properties of languages, not machines. Let the notation n(M)n(M) denote the number of states in an arbitrary TM\text{TM}, MM. The following language/problem is recursive/decidable:

Get hands-on with 1200+ tech skills courses.