Kleene's recursion theorem
ProvedFamousTheorems.kleene_recursion_theoremKleene's recursion theorem. If is a partial recursive function of a program code and an input , there is a program that computes , i.e. .
Programs can thus refer to their own code. The theorem gives quines, allows recursive definitions of computable functions to be justified directly, and yields short proofs of Rice's theorem and the undecidability of the halting problem. It is also a cornerstone of Gödel-style self-reference in computability theory.
Formalization note. Mathlib's Nat.Partrec.Code.fixed_point₂; Partrec₂ f says f is partial recursive in both arguments, and c.eval is the partial function computed by code c.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem kleene_recursion_theorem {f : Nat.Partrec.Code → ℕ →. ℕ} (hf : Partrec₂ f) : ∃ c : Nat.Partrec.Code, c.eval = f c := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Nat.Partrec.Code.fixed_point₂`. Proof here reduces to that Mathlib result.