Recursive Functions

This file was updated on 28th Oct, 2024, and it's not finished.

Intuitively, the notion of an effective computable function $f$ from natural numbers to natural numbers is the notion of a function for which there is a finite list of instructions that in principle make it possible to determine the value $f(x_1, \dots, x_n)$ for any arguments $x_1, \dots, x_n$.

We adopt the system in which the number zero id represented by the cipher $0$, and a natural number $n > 0$ is represented by the cipher $0$ followed by a sequence of $n$ little raised strokes or accents. Thus the numeral for one is $0'$, the numeral for two is $0''$, and so on.

3 Basic Functions

Zero Function

For any argument $x$, $z(x) = 0$.

$$z(0) = 0, z(0') = 0, z(0'') = 0, \dots$$

Successor Function

$$s(0) = 0', s(0') = 0'', s(0'') = 0''', \dots$$

Identity Function / Projection Function

For each positive integer $n$, there are $n$ identity functions of $n$ arguments, which pick out the first, second, \dots, and $n$-th of the arguments:

$$\text{id}^n_i(x_1, \dots, x_i, \dots, x_n) = x_i.$$

Operations

Composition / Substitution

If $f$ is a function of $m$ arguments and each of $g_1, \dots, g_m$ is a function of $n$ arguments, then the function obtained by composition from $f, g_1, \dots, g_m$ is the function $h$ where we have

$$\text{Cn: }h(x_1, \dots, x_n) = f \left( g_1(x_1, \dots, x_n), \dots, g_m(x_1, \dots, x_n) \right).$$

This expression can also be written as

$$h = \text{Cn} \left[ f, g_1, \dots, g_m \right].$$

Addition

$$x + 0 = x, \; x + y' = (x + y)'.$$

Multiplication

$$x \cdot 0 = 0, \; x \cdot y' = x + (x \cdot y).$$

Exponentiation

$$x^0 = 0', \; x^{y'} = x \cdot x^y.$$

Super-Exponentiation

$$x^{x^{x^{x^{\cdot^{\cdot^{\cdot}}}}}} \; (\text{a stack of } y \; x \text{s}) \equiv x \uparrow x \uparrow x \uparrow x \uparrow \dots \uparrow x \; (\text{a row of } y \; x \text{s}) \equiv x \Uparrow y.$$ $$x \Uparrow 0 = 0', \; x \Uparrow y' = x \uparrow (x \Uparrow y).$$

Other Functions

Constant Function

For any natural number $n$, let the constant function $\text{const}_n$ be defined by $\text{const}_n (x) = n$ for all $x$.

$$\text{const}_0 (x) = 0 = z(x).$$ $$\text{const}_n (x) = n = s(\text{const}_{n-1} (x)) = \text{Cn} [s, \text{const}_{n-1}] (x), n \geq 1.$$

Sum Function

$$\text{sum} (x, 0) = x, \; \text{sum} (x, y') = \text{sum} (x, y)'.$$

Product Function

$$\text{prod} (x, 0) = z(x), \; \text{prod} (x, y') = x + \text{prod} (x, y).$$

Factorial Function

The factorial $x!$ for positive $x$ is the product $1 \times 2 \times 3 \times \cdots \times x$ of all positive integers up to and including $x$, and by convention $0! = 1$.

$$0! = 1, \; y'! = y! \cdot y'.$$

Primitive Recursion

$$\text{Pr: } \underline{h(x, 0) = f(x), \; h(x, y') = g(x, y, h(x, y))}. \\ \cdots \\ \text{Pr: } \underline{h(x_1, \dots, x_n, 0) = f(x_1, \dots, x_n), \; h(x_1, \dots, x_n, y') = g(x_1, \dots, x_n, y, h(x_1, \dots, x_n, y))}.$$

Where the underlined equations — called the recursion equations for the function $h$ — hold, $h$ is said to be definable by (primitive) recursion from the functions $f$ and $g$. In shorthand,

$$h = \text{Pr} [f, g].$$

Example 1 $\text{sum} = \text{Pr} \left[ \text{id}^1_1, \text{Cn} \left[s, \text{id}^3_3\right] \right].$

$$\text{sum} (x, 0) = x = \text{id}^1_1 (x) = f(x).$$ $$\text{sum} (x, y') = \text{sum} (x, y)' \Rightarrow \text{sum} (x, s(y)) = s(\text{sum} (x, y)).$$ $$\begin{array}{rll} \text{sum} (x, s(y)) & = & s(\text{sum} (x, y)) \\ & = & \text{Cn} [s, \text{id}^3_3] (x, y, \text{sum} (x, y)) \\ & = & g(x, y, \text{sum} (x, y)). \end{array}$$

Example 2 $\text{prod} = \text{Pr} [z, \text{Cn} [\text{sum}, \text{id}^3_1, \text{id}^3_3]].$

$$h(x, 0) = 0 = z(x) \Rightarrow f = z.$$

We know $\text{prod} (x, y') = x + \text{prod} (x, y)$, so

$$\begin{array}{rll} h(x, y') & = & g(x, y, h(x, y)) \\ & = & \text{id}^3_1 (x, y, h(x, y)) + \text{id}^3_3 (x, y, h(x, y)) \\ & = & \text{sum} (\text{id}^3_1 (x, y, h(x, y)), \text{id}^3_3 (x, y, h(x, y))) \\ & = & \text{Cn} [\text{sum}, \text{id}^3_1, \text{id}^3_3] (x, y, h(x, y)). \end{array}$$

That is

$$\text{Cn} [\text{sum}, \text{id}^3_1, \text{id}^3_3] = g.$$