Rice's Theorem

Rice's theorem is a sweeping generalization of the undecidability of the halting problem: any nontrivial semantic property of Turing machines is undecidable. This result has profound implications for program verification.

Statement

Theorem5.2Rice's Theorem

Let $P$ be a property of computably enumerable sets (i.e., $P \subseteq \{W_e : e \in \mathbb{N}\}$ ). If $P$ is nontrivial (neither empty nor the set of all c.e. sets), then the index set $\{e : W_e \in P\}$ is undecidable.

Proof

Without loss of generality, assume $\emptyset \notin P$ (otherwise consider $\bar{P}$ ). Let $W_a \in P$ for some $a$ . We reduce the halting problem $K$ to $\{e : W_e \in P\}$ .

Given $e$ , construct a Turing machine $M_e$ that on input $x$ : first simulates machine $e$ on input $e$ ; if it halts, then simulates machine $a$ on input $x$ .

If $e \in K$ (machine $e$ halts on $e$ ), then $W_{M_e} = W_a \in P$ . If $e \notin K$ , then $W_{M_e} = \emptyset \notin P$ . Thus $e \in K \iff M_e \in \{e : W_e \in P\}$ , so $K \leq_m \{e : W_e \in P\}$ . Since $K$ is undecidable, so is $\{e : W_e \in P\}$ . $\square$

■

Applications

ExampleConcrete Undecidable Properties

The following are undecidable by Rice's theorem:

"Does Turing machine $M$ accept the empty string?"
"Is the language of $M$ regular? Context-free? Finite? Infinite?"
"Does $M$ compute the identity function?"
"Is $W_e = \mathbb{N}$ ?"

Each is a nontrivial property of the c.e. set $W_e$ , hence undecidable.

RemarkLimitations of Rice's Theorem

Rice's theorem applies only to extensional (semantic) properties of programs — properties that depend only on the function computed, not on the program's syntax. Intensional (syntactic) properties, such as "does the program have fewer than 100 instructions" or "does the program contain a specific subroutine," may or may not be decidable and are not covered by Rice's theorem.