Rice's Theorem and Decidability

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 $E$, 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 $\text{TM}$s and not for others. All the reductions involving nontrivial properties of $\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)$ denote the number of states in an arbitrary $\text{TM}$, $M$. The following language/problem is recursive/decidable: