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.

Symbol	Unicode	Name	Meaning
Z	—	Zero	Constant zero
S	—	Successor	x + 1
Pⁿᵢ	—	Projection	Select i-th argument
μ	U+03BC	Minimization	Least-witness search

Metatheory. Primitive recursive ⊊ total recursive ⊊ partial recursive; Ackermann separates the first inclusion. The class coincides with Turing-computable functions. Provably-total functions of arithmetic theories stratify by ordinal strength.

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

Limitations. Total (primitive) subclass cannot capture all computable total functions. μ introduces partiality and undecidability. No account of running time.