Partial Computable Function

Definition

A partial computable function or partial recursive function is, in the Godel-Kleene presentation, a member of the smallest set of partial functions on the natural numbers containing the initial functions and closed under composition, primitive recursion, and unbounded minimization.

For each $n\in \mathbb{N}$, let ${\mathcal{R}}_n$ be the smallest family of partial functions ${\mathbb{N}}^n\rightharpoonup \mathbb{N}$ satisfying:

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

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}$$

Unbounded minimisation is defined by

$$\mu f(\vec{x})=\min \left\{y\in \mathbb{N}|f(\vec{x},y)=0\text{ and }f(\vec{x},z)\downarrow \ne 0\text{ for every }z<y\right\}.$$

Here $f(\vec{x},z)\downarrow$ means that the computation is defined. Thus the search diverges if:

• no zero is ever found, or
• some earlier computation $f(\vec{x},z)$ diverges.

Properties

The initial functions are total. Composition and primitive recursion preserve totality when their constituent functions are total. Unbounded minimisation may produce a partial function even when $f$ is total.

The functions in ${\mathcal{R}}_n$ are called the partial recursive functions. The total members are called the total recursive functions. By the equivalence theorem for standard models of computation, the partial recursive functions are exactly the partial computable functions.

Related Concepts

Primitive recursion

References

cutland1980-computability