The s-m-n theorem
ProvedFamousTheorems.smnThe s-m-n theorem (the parametrization theorem).
There is a computable function taking a program and a value to a program that runs with frozen as its first argument:
Partial application can be performed effectively on source code: specializing a program to a fixed input is itself a computable transformation of programs, not merely something an outside observer can do. The name comes from Kleene's original notation , where the function freezes of arguments.
Together with the universal machine it is one of the two pillars of computability theory: the two combine to give Kleene's recursion theorem, Rice's theorem, and the standard undecidability results. It is also the formal content behind currying in programming languages, and the reason partial evaluation is possible at all.
Formalization note. Nat.Partrec.Code is the type of codes for partial recursive
functions, eval interprets a code, Computable₂ is computability in two arguments, and
Nat.pair is the pairing function. The result is Mathlib's Nat.Partrec.Code.smn.
import Mathlib
namespace FamousTheorems
universe u v
open Filter Set Topology DirectSum
theorem smn : ∃ f : Nat.Partrec.Code → ℕ → Nat.Partrec.Code, Computable₂ f ∧
∀ c n x, Nat.Partrec.Code.eval (f c n) x =
Nat.Partrec.Code.eval c (Nat.pair n x) := by sorry
end FamousTheorems