The Ackermann function is not primitive recursive
ProvedFamousTheorems.ackermann_not_primitive_recursiveThe Ackermann function is not primitive recursive. Let be the Ackermann function, defined by , and . Then the diagonal is not a primitive recursive function.
The Ackermann function was the first example (Ackermann 1928, following Hilbert) of a total computable function that is not primitive recursive. It grows faster than every primitive recursive function, so primitive recursion does not capture all effective computation. This motivated the general recursive and -recursive functions.
Formalization note. Mathlib's not_nat_primrec_ack_self. ack is the two-argument Ackermann function above, and Nat.Primrec is the inductive predicate of primitive recursive functions . Non-primitive-recursiveness of the diagonal implies that of ack itself.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems theorem ackermann_not_primitive_recursive : ¬Nat.Primrec fun n : ℕ => ack n n := by sorry end FamousTheorems
Source
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `not_nat_primrec_ack_self`. Proof here reduces to that Mathlib result.