10.1 Recursive Functions

Recursive function theory gives a mathematical definition of computable numerical functions by specifying basic functions and closure operations that generate increasingly complex functions from simple ones, and this framework allows one to reason about computation purely within arithmetic.

All functions considered in this section have inputs and outputs in the natural numbers:

\mathbb{N} = \{0,1,2,\dots\}.

An $n$ ary function is written:

f : \mathbb{N}^n \to \mathbb{N},

and the number $n$ is called the arity of the function.

Initial Functions

We begin with three basic types of functions, which are taken as primitive building blocks.

Definition 10.1 (Zero Function)

For each $n \geq 1$ , the zero function is:

Z_n : \mathbb{N}^n \to \mathbb{N}, \quad Z_n(x_1,\dots,x_n)=0.

Definition 10.2 (Successor Function)

The successor function is:

S : \mathbb{N} \to \mathbb{N}, \quad S(x)=x+1.

Definition 10.3 (Projection Functions)

For $1 \leq i \leq n$ , define:

P_i^n : \mathbb{N}^n \to \mathbb{N}, \quad P_i^n(x_1,\dots,x_n)=x_i.

Composition

Definition 10.4 (Composition)

Let:

g : \mathbb{N}^k \to \mathbb{N}

and:

h_1,\dots,h_k : \mathbb{N}^n \to \mathbb{N}.

Define:

f(x_1,\dots,x_n) = g\big(h_1(x_1,\dots,x_n),\dots,h_k(x_1,\dots,x_n)\big).

Then $f$ is obtained from $g$ and the $h_i$ by composition.

Primitive Recursion

Definition 10.5 (Primitive Recursion)

Let:

g : \mathbb{N}^n \to \mathbb{N}, \quad h : \mathbb{N}^{n+2} \to \mathbb{N}.

Define:

f : \mathbb{N}^{n+1} \to \mathbb{N}

by:

f(x_1,\dots,x_n,0)=g(x_1,\dots,x_n),

f(x_1,\dots,x_n,y+1) = h(x_1,\dots,x_n,y,f(x_1,\dots,x_n,y)).

Definition 10.6 (Primitive Recursive Function)

The class of primitive recursive functions is the smallest class containing $Z_n$ , $S$ , and $P_i^n$ , and closed under composition and primitive recursion.

Example 10.7 (Addition)

Define:

\operatorname{add}(x,0)=x,

\operatorname{add}(x,y+1)=S(\operatorname{add}(x,y)).

Then addition is primitive recursive.

Proof

The base function is:

g(x)=x=P_1^1(x).

The step function is:

h(x,y,z)=S(z)=S(P_3^3(x,y,z)).

Both are primitive recursive, so addition is primitive recursive.

Example 10.8 (Multiplication)

Define:

\operatorname{mul}(x,0)=0,

\operatorname{mul}(x,y+1)=\operatorname{add}(\operatorname{mul}(x,y),x).

Proof

The base function is:

g(x)=0=Z_1(x).

The step function is:

h(x,y,z)=\operatorname{add}(z,x) = \operatorname{add}(P_3^3(x,y,z),P_1^3(x,y,z)).

Thus multiplication is primitive recursive.

Example 10.9 (Exponentiation)

Define:

\operatorname{exp}(x,0)=1,

\operatorname{exp}(x,y+1)=\operatorname{mul}(\operatorname{exp}(x,y),x).

Proof

The constant function $1$ is primitive recursive since:

1 = S(0) = S(Z_1(x)).

The step function:

h(x,y,z)=\operatorname{mul}(z,x)

is primitive recursive by composition.

Thus exponentiation is primitive recursive.

Definition 10.10 (Predecessor)

Define:

\operatorname{pred}(0)=0,

\operatorname{pred}(y+1)=y.

Lemma 10.11

The predecessor function is primitive recursive.

Proof

Use primitive recursion with:

g=0,

h(y,z)=y=P_1^2(y,z).

Thus $\operatorname{pred}$ is primitive recursive.

Definition 10.12 (Truncated Subtraction)

Define truncated subtraction by:

x - 0 = x,

x - (y+1) = \operatorname{pred}(x - y).

This function agrees with ordinary subtraction when $x \ge y$ , and returns $0$ when $x < y$ , since repeated application of the predecessor function never produces negative values.

Lemma 10.13

Truncated subtraction is primitive recursive.

Proof

Base:

g(x)=x.

Step:

h(x,y,z)=\operatorname{pred}(z)=\operatorname{pred}(P_3^3(x,y,z)).

Thus primitive recursive.

Definition 10.14 (Minimization)

Let:

f : \mathbb{N}^{n+1} \to \mathbb{N}.

Define:

g(x_1,\dots,x_n) = \mu y \,[ f(x_1,\dots,x_n,y)=0 ].

This returns the least $y$ such that $f(x_1,\dots,x_n,y)=0$ , if such a $y$ exists, and is undefined otherwise.

Definition 10.15 (Partial Recursive Function)

The class of partial recursive functions is obtained from the initial functions by closure under composition, primitive recursion, and minimization.

Definition 10.16 (General Recursive Function)

A function is general recursive if it is partial recursive and defined for all inputs.

Theorem 10.17

Every primitive recursive function is general recursive.

Proof

Primitive recursive functions are built from the initial functions using composition and primitive recursion.

The class of partial recursive functions contains the initial functions and is closed under these operations.

Thus every primitive recursive function is partial recursive.

Since primitive recursive functions are total, they are general recursive.

Remarks

Primitive recursion captures computations that always terminate with a bounded number of steps determined by the input, while minimization introduces unbounded search and allows the definition of functions that may fail to terminate on some inputs, which leads naturally to the study of partial computable functions.