Existence of a universal partial recursive function
ProvedFamousTheorems.universal_partial_recursive_function_7aExistence of a universal partial recursive function. Let be the standard enumeration of the partial recursive functions by codes . The evaluation function
is itself partial recursive.
This is Kleene's enumeration theorem, the recursion-theoretic analogue of Turing's universal machine. Together with the s-m-n theorem it underlies Kleene's recursion theorem, the undecidability of the halting problem and Rice's theorem.
Formalization note. Mathlib's Nat.Partrec.Code.eval_part. Nat.Partrec.Code is Mathlib's syntax of partial recursive function codes, with an encoding into . Nat.Partrec.Code.eval c n is the result, possibly undefined, of running code on input . Partrec₂ means partial recursive as a function of two arguments.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems theorem universal_partial_recursive_function_7a : Partrec₂ Nat.Partrec.Code.eval := by sorry end FamousTheorems
Source
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Nat.Partrec.Code.eval_part`. Proof here reduces to that Mathlib result.