Primitive Recursion

Definition

Primitive recursion is an operation for defining a function on the natural numbers by giving its value at $0$ and a rule for computing its value at $n+1$ from its value at $n$.

For each $n\in \mathbb{N}$, let ${\mathcal{P}}_n$ be the smallest family of total functions ${\mathbb{N}}^n\to \mathbb{N}$ containing the initial functions and closed under composition and primitive recursion:

$$\frac{}{\mathrm{zero}:{\mathcal{P}}_0}\frac{}{\mathrm{suc}:{\mathcal{P}}_1}\frac{1\le i\le n}{{\mathrm{proj}}_i^n:{\mathcal{P}}_n}$$ $$\frac{f:{\mathcal{P}}_{n}g:{\mathcal{P}}_{n+2}}{{\rho }_n(f,g):{\mathcal{P}}_{n+1}}\frac{g:{\mathcal{P}}_k[f_i:{\mathcal{P}}_m{]}_{i<k}}{g\circ [f_i{]}_{i<k}:{\mathcal{P}}_m}.$$

Equivalently, if $f:{\mathbb{N}}^n\to \mathbb{N}$ and $g:{\mathbb{N}}^{n+2}\to \mathbb{N}$, then the function $h:{\mathbb{N}}^{n+1}\to \mathbb{N}$ defined by primitive recursion satisfies $h(\vec{x},0)=f(\vec{x})$ and $h(\vec{x},y+1)=g(\vec{x},y,h(\vec{x},y))$.

Interpretation

These operations are interpreted as follows:

$$\begin{array}{rl}\mathrm{zero}()& =0,\\ \mathrm{suc}(n)& =n+1,\\ {\mathrm{proj}}_i^n(a_1,\dots ,a_n)& =a_i,\\ {\rho }_n(f,g)(\vec{x},0)& =f(\vec{x}),\\ {\rho }_n(f,g)(\vec{x},y+1)& =g(\vec{x},y,{\rho }_n(f,g)(\vec{x},y)),\\ (g\circ [⟨f_i⟩{]}_{i<k})(\vec{x})& =g(f_0(\vec{x}),\dots ,f_{k-1}(\vec{x})).\end{array}$$

Properties

Primitive recursion preserves totality: if $f$ and $g$ are total, then $h$ is total.

Starting from the initial functions and closing under composition and primitive recursion yields the class of primitive recursive functions. Allowing in addition unbounded minimization yields the larger class of partial computable functions.

Examples

Addition can be defined by primitive recursion on the second argument:

$$\begin{array}{rl}\mathrm{add}(x,0)& =x,\\ \mathrm{add}(x,y+1)& =\mathrm{suc}(\mathrm{add}(x,y)).\end{array}$$

Related Concepts

Partial Computable Function
Unbounded Minimization

References

cutland1980-computability