Rice’s Theorem (Undecidability of All Nontrivial Semantic Properties)

Rice’s theorem is a foundational result in computability theory: it proves that you cannot decide, for an arbitrary program (Turing machine), most meaningful questions about the language (the set of inputs it accepts). The key idea is that any decision problem depending only on the semantics of a machine’s accepted language—and not on superficial syntax—must be undecidable as long as the property is nontrivial.

In standard form, we consider languages over $\Sigma^*$ that are accepted by Turing machines, and a property $P$ of such languages. Rice’s theorem says that if $P$ is nontrivial (true for at least one accepted language, false for at least one accepted language) then the set of machines whose accepted language has property $P$ is undecidable. (Equivalently: there is no total computable decider for the property.)

Nontriviality and semantic dependence are essential:

• Semantic: only $L(M)$ matters, not the description of $M$.
• Nontrivial: both outcomes occur among accepted languages.

Rice’s theorem provides a unifying framework for proving undecidability results that look different at first glance—such as deciding whether a program’s accepted language is empty, finite, infinite, includes a particular string, etc.—by showing they fit the template “nontrivial property of $L(M)$.”

Core terminology (what Rice’s theorem quantifies over)

Let $M$ be a Turing machine and $L(M)$ be the language it recognizes/accepts.

We define a property $P$ on languages:

• $P$ is semantic if for any two Turing machines $M_1, M_2$,
  $L(M_1)=L(M_2)\implies (P(L(M_1))\Leftrightarrow P(L(M_2))).$
• $P$ is nontrivial if there exists at least one machine $M_{\text{yes}}$ with
  $P(L(M_{\text{yes}}))=\text{true}$
  and at least one machine $M_{\text{no}}$ with
  $P(L(M_{\text{no}}))=\text{false}.$

Then define the decision problem:

• Input: a description of a Turing machine $M$
• Question: does $P(L(M))$ hold?

Rice’s theorem states that if $P$ is nontrivial and semantic, then this decision problem is undecidable.

Why “short note” still needs the quantifiers

Rice’s theorem is powerful because it is universal over properties: it doesn’t matter which property you pick (emptiness, infiniteness, universality, etc.) as long as it’s a nontrivial semantic property. The proof works by reducing from a known undecidable problem (commonly via a many-one reduction from the halting problem or from Rice-style self-reference constructions).

Key learning terms:

• Turing machine
• Language of a machine
• Semantic property
• Nontrivial property

Typical applications (what Rice’s theorem instantly rules out)

Rice’s theorem is often used in the form: “Given any nontrivial semantic property, the corresponding index set is undecidable.”

Common examples of properties that fit the theorem:

• Emptiness of the language (property $P(L)= (L=\emptyset)$) is nontrivial.
• Finiteness (for many models, finiteness is nontrivial).
• Infiniteness is nontrivial.
• Whether a given string is accepted (e.g., $P(L)=(s\in L)$) is semantic and nontrivial.

In each case, you show there exist machines that make the property true and machines that make it false; then Rice’s theorem gives undecidability immediately.