Rice's theorem
ProvedFamousTheorems.rice_theoremRice's theorem. Let be a set of partial functions . If membership of the function computed by a program in is decidable, then contains either all partial recursive functions or none of them.
Every nontrivial semantic property of programs is therefore undecidable: whether a program halts on some input, computes a total function, or is equivalent to a given program. It generalises the undecidability of the halting problem and is the basic limitation on static program analysis.
Formalization note. Mathlib's ComputablePred.rice. Programs are codes Nat.Partrec.Code with semantics eval. The conclusion says that if one partial recursive f lies in C then every partial recursive g does.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem rice_theorem (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c : Nat.Partrec.Code => c.eval ∈ C) {f g : ℕ →. ℕ}
(hf : Nat.Partrec f) (hg : Nat.Partrec g) (fC : f ∈ C) : g ∈ C := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `ComputablePred.rice`. Proof here reduces to that Mathlib result.