Existing in Mathlib · Computability and logic

Rice's Theorem

Suppose a semantic property of partial functions can be decided computably from program codes. If one partial-recursive function has that property, then every partial-recursive function has it.

program code
partial recursive function
semantic property
computable predicate
semantic undecidability

Exact theorem

Exact Mathlib statement

theorem ComputablePred.rice (C : Set (ℕ →. ℕ)) (h : ComputablePred fun c => Nat.Partrec.Code.eval c ∈ C) {f g} (hf : Nat.Partrec f) (hg : Nat.Partrec g) (fC : f ∈ C) : g ∈ C

The theorem at a glance

Rice's theorem at a glance

A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.

An ivory, forest-green, and gold Rice theorem poster sends program codes through evaluation, shows partial-recursive f inside a semantic property, and uses a self-reference loop to force arbitrary partial-recursive g into the same property. — Computable semantic membership and one admitted partial-recursive witness force every partial-recursive function into the property.

Statement structure

From hypotheses to conclusion

This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.

Five perforated program-code cards feed one evaluator; a bundle of partial-function traces passes through a one-way self-reference loop and every displayed trace enters the same semantic region C. — Evaluated partial-recursive behaviors pass through one self-reference route into the same semantic property that already contains a witness.

Why it matters

A mathematical landmark

Rice's theorem draws a foundational boundary around algorithmic reasoning about programs: a computable decision procedure cannot separate partial-recursive functions by a nontrivial semantic property. Mathlib's selected endpoint proves this through a self-referential code in its partial-evaluation model.

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally

Locally reproducedExact upstream declaration replayed

Reviewed pageCurrent public presentation reviewed

Accepted Atlas resultNot recorded for the preferred artifact

Mathlib is the source of the theorem; the local Lean replay and page review are separate.

Claim boundary

No new theorem is claimed

This target indexes Mathlib's implication form of Rice's theorem. For a semantic property C of partial functions, assume program-code membership through eval is computable. If one partial-recursive f belongs to C, then every partial-recursive g belongs to C. It is specific to Mathlib's partial-function and program-code model and does not classify arbitrary syntactic code properties or all noncomputable semantic properties.

Proof Atlas did not originate Rice's theorem or Mathlib's declaration.
The formal statement is tied to Mathlib's `Nat.Partrec` and `Nat.Partrec.Code` representation, not every machine model simultaneously.
The hypothesis decides a property of evaluated partial functions from their program codes; the theorem does not classify arbitrary syntactic properties of codes.
The conclusion ranges over partial-recursive f and g, not all arbitrary partial functions.
This endpoint is a one-way implication, not the separate rice₂ empty-or-universal equivalence.
The generated explanation and visuals are not proof evidence.

Source and local evidence

Where the theorem comes from

Existing declaration: ComputablePred.rice in mathlib
Relationship: The checked artifact is the upstream declaration itself
Local Lean evidence: artifact.library.mathlib.rice-theorem.v001
Source: Open the pinned upstream reference