Definition 2.1.1 (Partial recursive function). The class of recursive functions is the smallest class of partial functions of the form ${\mathbb{N}}^k\to \mathbb{N}$ that contains the basic functions:

• Projections: ${\mathrm{\Pi }}_i^m:(n_1,\dots ,n_m)\mapsto n_i$;

• Successor: $S^{+}:n\mapsto n+1$;

• Zero: $z:n\mapsto 0$

and is closed under:

• Compositions: if $g:{\mathbb{N}}^k\to \mathbb{N}$ is partial recursive and so are $h_1,\dots ,h_k:{\mathbb{N}}^m\to \mathbb{N}$, then the function $f:{\mathbb{N}}^m\to \mathbb{N}$ given by $f(\overline{n})=g(h_1(\overline{n}),\dots ,h_k(\overline{n}))$ is partial recursive.

• Primitive recursion: Given partial recursive functions $g:{\mathbb{N}}^m\to \mathbb{N}$ and $h:{\mathbb{N}}^{m+2}\to \mathbb{N}$, the function $f:{\mathbb{N}}^{m+1}\to \mathbb{N}$ defined by

  $$\{\begin{array}{c}f(0,\overline{n}):=g(\overline{n})\hfill \\ f(k+1,\overline{n}):=h(f(k,\overline{n}),k,\overline{n})\hfill \end{array}$$

• Minimisation: Suppose $g:{\mathbb{N}}^{m+1}\to \mathbb{N}$ is partial recursive. Then the function $f:{\mathbb{N}}^m\to \mathbb{N}$ that maps $\overline{n}$ to the least $n$ such that $g(n,\overline{n})=0$ (if it exists) is partial recursive.

  Notation: $f(\overline{n})=\mu n.g(n,\overline{n})=0$.

The class of functions produced by the same conditions but excluding minimisation is called the class of primitive recursive functions.

A partial recursive function that is defined everywhere is called a total recursive function.