Rice's Theorem: Every Nontrivial Semantic Property of Programs Is Undecidable

The precise statement

Fix a Gödel numbering (φₑ)ₑ∈ℕ of the partial computable functions, so φₑ is the function computed by the program with index e. A property is a set P of partial computable functions; its index set is I(P) = { e ∈ ℕ : φₑ ∈ P }. Note I(P) is extensional: if φₑ = φⱼ (same function) then e ∈ I(P) ⇔ j ∈ I(P). This is what makes P a property of behavior, not of syntax.

Rice's Theorem. I(P) is decidable (recursive) if and only if P is trivial, meaning P = ∅ or P is the set of all partial computable functions. Equivalently: for every set P with ∅ ⊊ P ⊊ {all partial computable functions}, the index set I(P) is undecidable.

The two hypotheses are load-bearing and named explicitly: extensionality (P is a set of functions, so I(P) can't distinguish two programs computing the same map) and nontriviality (both P and its complement are nonempty).

The picture: you only ever see behavior through a keyhole

Imagine you are handed a program and asked, "does this compute the squaring function?" You may run it on 0, 1, 2, … forever, and it may agree with n² on every input you try — yet you can never rule out that on input 10⁶ it silently enters an infinite loop or returns 42. Semantic questions are Σ-shaped: confirming behavior may require watching infinitely many computations, some of which never halt.

Rice's insight is that this keyhole is not merely inconvenient — it is fundamental. Any nontrivial behavioral question is at least as hard as "does this machine halt?" The intuition for why: to decide P you'd have to detect, from the code alone, a fact about the limiting input/output map, and you can hide a copy of an arbitrary halting computation inside a program's behavior. Deciding P would then decide halting. Because every nontrivial P admits this hiding trick, the whole spectrum of behavioral properties collapses to undecidable.

Key idea of the proof: reduce the halting problem

We show the halting problem K = { x : φₓ(x)↓ } many-one reduces to I(P) (or to its complement). Since P is nontrivial, pick a witness function in P and one outside it. A convenient normalization: let ⊥ be the everywhere-undefined function (computed by a program that just loops). WLOG assume ⊥ ∉ P (otherwise run the argument on the complement of P, which is also nontrivial). Because P ≠ ∅, choose a fixed function g ∈ P with a program index a, so φₐ = g.

Now define, from an input x, a new program with the following behavior on input y:

ψₓ(y) = "first run φₓ(x); if it halts, then output φₐ(y); otherwise diverge."

By the s-m-n theorem there is a total computable function s with φ_{s(x)} = ψₓ. Trace the two cases: if x ∈ K, then φₓ(x)↓, so ψₓ(y) = φₐ(y) = g(y) for all y, hence φ_{s(x)} = g ∈ P. If x ∉ K, then φₓ(x)↑, so ψₓ diverges everywhere: φ_{s(x)} = ⊥ ∉ P. Thus x ∈ K ⇔ s(x) ∈ I(P). Since K is undecidable and s is computable, I(P) is undecidable. ∎

Worked example: "does this program ever print HELLO?"

Let P = { f : f(y) is defined and equals the string "HELLO" for at least one y }. This is semantic (it depends only on the function f) and nontrivial (the constant-"HELLO" function is in P; the everywhere-undefined function ⊥ is not). Rice immediately gives undecidability — but let's see the reduction concretely.

Here g = the constant function y ↦ "HELLO", with some index a; ⊥ ∉ P. Given x, build the program: on input y, simulate φₓ(x); if that simulation halts, print "HELLO"; else loop. Call its index s(x). If x halts on x, this program prints "HELLO" on every input → s(x) ∈ I(P). If x runs forever on x, this program never prints anything → s(x) ∉ I(P). A decider for "ever prints HELLO" would therefore decide the halting problem. Contradiction — so no virus-scanner-style "does it ever do X?" checker can be complete and correct for all programs.

Why the hypotheses matter — and what breaks without them

Drop extensionality and everything is fine. Syntactic questions escape Rice completely: "does the source contain a specific opcode?", "is the code fewer than 100 symbols?", "does it use recursion in the parse tree?" are all decidable — you inspect the string, never the behavior. Rice says nothing about these because their sets are not index sets.

Drop nontriviality and it's vacuous. If P is everything, I(P) = ℕ (always accept); if P is empty, I(P) = ∅ (always reject). Both trivially decidable.

Semidecidability is subtler. Rice's Theorem forbids decidability, not always semidecidability. The Rice–Shapiro theorem characterizes which P have computably enumerable index sets: exactly those P that are "open" in the sense of being determined by finite partial information (monotone and compact). "φₑ(0)↓" is c.e.; "φₑ is total" is not even c.e. (it is Π₂-complete). So undecidability comes in strengths, and Rice is the first, coarsest layer.

Significance: the ceiling on program analysis

Rice's Theorem is the theoretical bedrock — and the fundamental limit — of static analysis, verification, and security. It says that perfect, general-purpose tools are impossible: no algorithm can decide, for all programs, whether they halt, whether two programs are equivalent, whether a program is malware (any purely-behavioral definition), whether an optimization preserves semantics, or whether dead code is truly unreachable. This is why compilers, type checkers, and verifiers are conservative — they use sound but incomplete approximations (abstract interpretation, model checking with bounded state, type systems), accepting false alarms to stay decidable.

Historically it packages the halting problem (Turing, 1936) into a single universal statement and sits beside Gödel's incompleteness and the undecidability of Hilbert's Entscheidungsprobem as a pillar of the negative results of logic. Its refinements — Rice–Shapiro, the arithmetical hierarchy classification of index sets (many are Σ₂- or Π₂-complete), and Kleene's recursion theorem lurking behind the s-m-n gadget — map the exact difficulty of every question you might ask about what a program does.

Which program properties are decidable? Semantic (behavioral) vs. syntactic, trivial vs. nontrivial.

Property of program e	Semantic or syntactic?	Nontrivial?	Decidable?
φₑ(0)↓ (halts on input 0)	Semantic	Yes	No — undecidable by Rice
φₑ computes a total function	Semantic	Yes	No (in fact Π₂-complete)
φₑ is the everywhere-undefined function	Semantic	Yes	No — undecidable
φₑ ∈ (all partial computable functions)	Semantic	No (trivial)	Yes — always accept
e contains a MULT instruction	Syntactic	Yes	Yes — inspect the source
The source code of e has < 100 symbols	Syntactic	Yes	Yes — measure the string