Rice's Theorem

Origin. Rice (1953). Sweeping undecidability result: every non-trivial semantic property of programs is undecidable. Generalizes the halting problem to all extensional properties.

Models. A property of the function a program computes — not of its code — cannot be decided from the code, unless the property is trivial (holds for all or for none).

Formalism.

Index set: For a class C of partial recursive functions, A = {e : φ_e ∈ C}. Extensional: depends only on the computed function.

Rice's theorem: A is recursive iff C = ∅ or C = all partial recursive functions. Every non-trivial C gives an undecidable index set.

Proof sketch: Fix f₀ ∈ C, f₁ ∉ C (or symmetric). Reduce K to A using s-m-n and the recursion theorem. Decidability of A would decide K.

Examples (all undecidable): Totality: {e : φ_e total}. Emptiness of domain: {e : dom(φ_e) = ∅}. Computing a fixed constant. Equivalence φ_e = φ_i.

Rice–Shapiro refinement: The theorem is a necessary condition only. If A = {e : φ_e ∈ C} is r.e., then for every partial recursive f, f ∈ C iff some finite θ ⊆ f has θ ∈ C. (Upward closure follows: if θ ⊆ f ⊆ g and θ ∈ C then g ∈ C.)

The converse fails as stated. The finite-approximation condition is a topological condition — it says C is open in the Scott topology — and openness alone does not make an index set r.e., since C may collect a non-r.e. family of finite functions. The converse needs an effectiveness hypothesis: if in addition the set of canonical indices of finite functions in C is r.e., then A is r.e. That is the Myhill–Shepherdson direction, and together the two say index sets are r.e. exactly when C is effectively open.

Using it: {e : φ_e total} is not even r.e. Take f total, so f ∈ C; Rice–Shapiro would give a finite θ ⊆ f with θ ∈ C, but no finite function is total.

Intensional escape: Properties of the code (states, syntax) can be decidable. "Has exactly five instructions" is decidable — not extensional.

Symbols.

Metatheory. Rice (1953) proved that an index set is recursive only in the two trivial cases, C empty or C everything; the argument reduces K to A using the s-m-n theorem, and it needs only that the numbering is acceptable — that it admits a universal function and s-m-n — so it applies to every general-purpose programming language and not merely to Turing machines. The refinement at the next level is a matched pair. Rice–Shapiro gives a necessary condition for A to be r.e.: f ∈ C iff some finite θ ⊆ f lies in C, which says C is open in the Scott topology on partial functions. That condition is not sufficient, because C can be a topologically open class collecting a non-r.e. family of finite functions; Myhill and Shepherdson supply the missing hypothesis, that the canonical indices of the finite functions in C be r.e., and with it the converse holds. Together they place index sets at the r.e. level exactly when C is effectively open. The theorem's immediate consequences are sharp: {e : φ_e total} is not r.e., since no finite function is total, and it is in fact Π⁰₂-complete.

Applies to. Limits of static analysis and verification. Compiler optimization boundaries. Program-equivalence undecidability. Abstract interpretation motivation.

Limitations. The theorem separates decidable from undecidable and says nothing finer: it does not locate an index set in the arithmetical hierarchy, and the actual placements range from Σ⁰₁-complete for non-emptiness of the domain through Π⁰₂-complete for totality to Σ⁰₃-complete for recursiveness of W_e, none of which Rice's argument delivers. It requires an acceptable numbering, so it does not apply to systems without a universal program — language equivalence for deterministic finite automata is decidable — and it therefore constrains general-purpose languages only. Extensionality is not incidental but necessary: intensional properties of code, such as instruction count or syntactic shape, may be decidable, and any analysis willing to be code-sensitive escapes the theorem. It forbids exact decision, not approximation, which is why sound incomplete analyses and abstract interpretation remain available and why the result motivates rather than blocks static analysis. It is entirely silent on resources, and it covers only properties of the function computed, not relations between programs or their running times.

© 2026 Lingenic LLC