Recursive Functions

Origin. Dedekind and Skolem formalized primitive recursion; Gödel, Herbrand, and Kleene defined the general recursive functions (1930s). A syntactic characterization of the computable number-theoretic functions.

Models. Functions on ℕ built from base functions by explicit schemes. Primitive recursive without minimization (all total); general (partial) recursive by adding unbounded search.

Formalism.

Initial functions: Zero: Z(x) = 0. Successor: S(x) = x + 1. Projections: Pⁿᵢ(x₁,...,xₙ) = xᵢ.

Composition: h(x̄) = f(g₁(x̄), ..., gₖ(x̄)).

Primitive recursion: f(x̄, 0) = g(x̄). f(x̄, y+1) = h(x̄, y, f(x̄, y)).

Primitive recursive class: Closed under composition and primitive recursion. All total. Includes +, ×, exp, bounded quantifiers, pairing.

Ackermann function: Total and computable, not primitive recursive. Grows faster than every primitive recursive function.

Minimization: f(x̄) = μy. [g(x̄, y) = 0] — least y making g zero. May be undefined (partial).

General recursive: Primitive recursion plus μ. μ-recursive = partial recursive = Turing computable.

Symbols.

Metatheory. Ackermann (1928) exhibited a total computable function that is not primitive recursive, later simplified by Péter (1935); it separates the classes because a diagonal argument shows there is no primitive recursive universal function for the primitive recursive functions, while the partial recursive functions do have a universal member. That asymmetry is exactly why μ must be added. Kleene's normal form theorem (1936) then shows one application of μ suffices: every partial recursive f has the form U(μy T(e, x̄, y)) with T primitive recursive. Kleene (1936) proved general recursiveness coextensive with λ-definability and Turing (1937) proved both coextensive with Turing computability. The total subclasses stratify by proof strength: the provably total functions of primitive recursive arithmetic are the primitive recursive functions, those of IΣ₁ are the same by Parsons' theorem, and those of Peano arithmetic are exactly the functions provably recursive using transfinite induction below ε₀, characterized by the fast-growing hierarchy F_α for α < ε₀. Grzegorczyk's hierarchy (1953) refines the primitive recursive class into levels ℰⁿ whose union is the whole class, with ℰ³ the Kalmár elementary functions.

Applies to. Definition of computability. Proof theory (provably total functions). Coding syntax for Gödel's theorems. Complexity of total functions.

Limitations. The primitive recursive class cannot enumerate itself: no primitive recursive function is universal for it, and Ackermann's function is a concrete total computable function it omits. The total recursive functions are no better placed, and worse in a specific way — the index set {e : φ_e total} is Π⁰₂-complete, so the total functions admit no effective enumeration at all, and any language whose programs are all total therefore fails to express some computable total function. Adding μ supplies the missing functions and introduces partiality: whether a μ-expression denotes is Σ⁰₁-complete, and whether two definitions give the same function is undecidable. The schemes carry no resource measure — nothing in the presentation records time or space, and Blum's speedup theorem shows some functions have no optimal program in any case. The characterizations of provably total functions are exact but relative: they presuppose a system of ordinal notations, and the ordinal assigned to a theory depends on that choice. The syntactic definition establishes nothing about effectivity without the Church–Turing thesis, which is not a theorem.

© 2026 Lingenic LLC