The Ackermann function

The primitive recursive functions are total and computable. They are not all the total computable functions: in 1928 Ackermann, a student of Hilbert, exhibited a function defined by a nested recursion on two variables, which grows faster than every primitive recursive function. We use the two-argument version introduced by Rózsa Péter (1935), in the simplified form given by Raphael Robinson (1948).

7.1 Definition and computability

Definition 7.1.#

The Ackermann–Péter function $A : \nat^2 \to \nat$ is defined by

$$\begin{aligned} A(0, y) &= y + 1, \\ A(x + 1, 0) &= A(x, 1), \\ A(x + 1, y + 1) &= A(x, A(x + 1, y)). \end{aligned}$$

These equations define a unique total function. Indeed, order $\nat^2$ lexicographically: $(x', y') <_{\mathrm{lex}} (x, y)$ if $x' < x$, or $x' = x$ and $y' < y$. This is a well-order. In each equation, the right-hand side only involves values of $A$ at pairs lexicographically smaller than the left-hand side: $(x, 1) <_{\mathrm{lex}} (x+1, 0)$, $(x+1, y) <_{\mathrm{lex}} (x+1, y+1)$, and $(x, z) <_{\mathrm{lex}} (x+1, y+1)$ whatever $z = A(x+1, y)$ is. By well-founded induction along $<_{\mathrm{lex}}$, $A(x, y)$ is defined for all $(x, y)$.

The first rows are easy to compute (see the exercises):

$$A(1, y) = y + 2, \qquad A(2, y) = 2y + 3, \qquad A(3, y) = 2^{y+3} - 3,$$

and $A(4, y) + 3$ is a tower of $y + 3$ twos: $A(4, 2) = 2^{65536} - 3$.

$A$ is computable. The equations can be used as rewriting rules. Represent the current state of the computation by a stack of integers $[z_1, \dots, z_r]$, standing for the expression $A(z_1, A(z_2, \dots A(z_{r-1}, z_r) \dots))$. Start with $[x, y]$ and, while the stack has at least two elements, rewrite its last two elements $z_{r-1}, z_r$:

• if $z_{r-1} = 0$, replace them by $z_r + 1$;
• if $z_{r-1} > 0$ and $z_r = 0$, replace them by $z_{r-1} - 1, 1$;
• if $z_{r-1} > 0$ and $z_r > 0$, replace them by $z_{r-1} - 1, z_{r-1}, z_r - 1$.

Each step preserves the value of the represented expression. For termination, we show by induction along $<_{\mathrm{lex}}$ that for every pair $(x, y)$ and every list $\vec u$, the algorithm transforms the stack $[\vec u, x, y]$ into $[\vec u, A(x, y)]$ in finitely many steps, without touching $\vec u$ before that. If $x = 0$, one step suffices. If $x > 0$ and $y = 0$, one step gives $[\vec u, x - 1, 1]$, and the induction hypothesis applies to $(x - 1, 1)$. If $x, y > 0$, one step gives $[\vec u, x - 1, x, y - 1]$; the induction hypothesis for $(x, y - 1)$, with the list $\vec u, x - 1$, leads to $[\vec u, x - 1, A(x, y - 1)]$, and the induction hypothesis for $(x - 1, A(x, y - 1))$ leads to $[\vec u, A(x - 1, A(x, y - 1))] = [\vec u, A(x, y)]$. With $\vec u$ empty, the algorithm started on $[x, y]$ stops with the single element $A(x, y)$. Using the coding of the previous lesson, the stack is a single integer and each step is a primitive recursive operation on it; only the number of steps is not bounded in advance.

7.2 Monotonicity

Lemma 7.2.#

For all $x, y$:

1. $A(x, y) > y$;
2. $A(x, y + 1) > A(x, y)$;
3. $A(x + 1, y) \geq A(x, y + 1)$;
4. $A(x + 1, y) > A(x, y)$.

Consequently $A$ is strictly increasing in each argument.

Proof of Lemma 7.2.

1. By induction on $x$, and for each $x$ by induction on $y$. For $x = 0$, $A(0, y) = y + 1 > y$. Suppose the claim holds for $x$. Then $A(x + 1, 0) = A(x, 1) > 1 > 0$, and if $A(x + 1, y) > y$, then $A(x + 1, y + 1) = A(x, A(x + 1, y)) > A(x + 1, y) > y$, so $A(x+1, y+1) \geq y + 2$.
2. For $x = 0$ this is clear. For $x + 1$: $A(x + 1, y + 1) = A(x, A(x + 1, y)) > A(x + 1, y)$ by 1.
3. By induction on $y$. For $y = 0$ both sides are equal to $A(x, 1)$. Suppose $A(x + 1, y) \geq A(x, y + 1)$. By 1, $A(x, y + 1) \geq y + 2$, hence $A(x + 1, y) \geq y + 2$, and by 2 (applied repeatedly), $A(x + 1, y + 1) = A(x, A(x + 1, y)) \geq A(x, y + 2)$.
4. By 3 and 2: $A(x + 1, y) \geq A(x, y + 1) > A(x, y)$.

Lemma 7.3.#

For all $x_1, x_2, y$: $A(x_1, A(x_2, y)) < A(x_1 + x_2 + 2, y)$.

Proof of Lemma 7.3.

Let $x = \max(x_1, x_2)$. By monotonicity,

$$\begin{aligned} A(x_1, A(x_2, y)) &\leq A(x, A(x, y)) \\ &< A(x, A(x + 1, y)) \\ &= A(x + 1, y + 1) \\ &\leq A(x + 2, y) \\ &\leq A(x_1 + x_2 + 2, y), \end{aligned}$$

using successively monotonicity in both arguments, item 4 inside item 2 of Lemma 7.2, the definition of $A$, item 3, and $x + 2 \leq x_1 + x_2 + 2$.

7.3 Majorization

For $\vec x = (x_1, \dots, x_k)$ we write $|\vec x| = \max(x_1, \dots, x_k)$, with $|\vec x| = 0$ for the empty tuple ($k = 0$).

Theorem 7.4 (Majorization).#

For every primitive recursive function $f : \nat^k \to \nat$ there is $n \in \nat$ such that $f(\vec x) < A(n, |\vec x|)$ for all $\vec x$.

Proof of Theorem 7.4.

By induction on a derivation of $f$. Say that $f$ is bounded by $n$ if $f(\vec x) < A(n, |\vec x|)$ for all $\vec x$. Since $A$ is increasing in its first argument, a function bounded by $n$ is bounded by every $n' \geq n$.

Basic functions. $Z(x) = 0 < A(0, x)$; $S(x) = x + 1 < x + 2 = A(1, x)$; and $p^k_i(\vec x) = x_i \leq |\vec x| < A(0, |\vec x|)$.

Composition. Let $f(\vec x) = h(g_1(\vec x), \dots, g_m(\vec x))$, where $h, g_1, \dots, g_m$ are all bounded by $n$. Then $\max_i g_i(\vec x) < A(n, |\vec x|)$, hence by monotonicity and Lemma 7.3,

$$f(\vec x) < A\big(n, \max_i g_i(\vec x)\big) < A\big(n, A(n, |\vec x|)\big) < A(2n + 2, |\vec x|).$$

Primitive recursion. Let $f(\vec x, 0) = g(\vec x)$ and $f(\vec x, y + 1) = h(\vec x, y, f(\vec x, y))$, with $g$ and $h$ bounded by $n$. When $\vec x$ is empty ($k = 0$), $g$ is replaced by a constant $a$, and we choose $n$ such that moreover $a < A(n, 0)$; this is possible since $A(n, 0) \geq A(0, 0) + n = n + 1$ by item 4 of Lemma 7.2. We first show by induction on $y$ that

$$f(\vec x, y) < A(n + 1, |\vec x| + y). \qquad (\ast)$$

For $y = 0$: $f(\vec x, 0) = g(\vec x) < A(n, |\vec x|) < A(n + 1, |\vec x|)$. Suppose $(\ast)$ holds for $y$, and let $w = A(n + 1, |\vec x| + y)$. By Lemma 7.2 (1), $|\vec x| + y < w$, and by induction hypothesis $f(\vec x, y) < w$; so $|(\vec x, y, f(\vec x, y))| < w$. Hence

$$f(\vec x, y + 1) < A\big(n, |(\vec x, y, f(\vec x, y))|\big) < A(n, w) = A(n + 1, |\vec x| + y + 1).$$

Now let $K = |(\vec x, y)|$. Then $|\vec x| + y \leq 2K < 2K + 3 = A(2, K)$, and by $(\ast)$ and Lemma 7.3,

$$f(\vec x, y) < A(n + 1, A(2, K)) < A(n + 5, K).$$

So $f$ is bounded by $n + 5$.

Corollary 7.5.#

The function $a(n) = A(n, n)$ is total and computable, but not primitive recursive. Hence $A$ is not primitive recursive either.

Proof of Corollary 7.5.

If $a$ were primitive recursive, by Theorem 7.4 there would be $m$ such that $a(n) < A(m, n)$ for all $n$. For $n = m$, this gives $A(m, m) < A(m, m)$, a contradiction. If $A$ were primitive recursive, so would be $a = A \circ (p^1_1, p^1_1)$.

The argument is a diagonalization: $a$ escapes each function $A(m, \cdot)$ at the point $m$. The majorization theorem says more: every unary primitive recursive function $f$ is eventually dominated by $a$, since $f(x) < A(m, x) \leq A(x, x)$ for $x \geq m$.

7.4 A diagonal argument

The same conclusion can be obtained without any growth estimate, by a direct diagonalization over derivations. Derivations of unary primitive recursive functions are finite objects; fix a computable coding of them by integers, and let $f_0, f_1, f_2, \dots$ be the list of the functions they define (the integers that do not code derivations being assigned the zero function, say).

Theorem 7.6.#

The function $d(n) = f_n(n) + 1$ is total and computable, but not primitive recursive.

Proof of Theorem 7.6.

To compute $d(n)$, decode the derivation coded by $n$ and evaluate it on $n$ following Proposition 5.4; this always terminates. If $d$ were primitive recursive, it would be $f_e$ for some $e$, and then $d(e) = f_e(e) + 1 = d(e) + 1$.

Thus unbounded loops are necessary to compute all total computable functions — and with unbounded loops comes the possibility of non-termination. The next lesson adds unbounded search to the primitive recursive functions.

7.5 Exercises

Exercise 7.7 ★.

Prove that $A(1, y) = y + 2$, $A(2, y) = 2y + 3$ and $A(3, y) = 2^{y + 3} - 3$.

Solution

By induction on $y$ in each case. $A(1, 0) = A(0, 1) = 2$ and $A(1, y + 1) = A(0, A(1, y)) = A(1, y) + 1$. Then $A(2, 0) = A(1, 1) = 3$ and $A(2, y + 1) = A(1, A(2, y)) = A(2, y) + 2$. Finally $A(3, 0) = A(2, 1) = 5 = 2^3 - 3$ and $A(3, y + 1) = A(2, A(3, y)) = 2 A(3, y) + 3 = 2(2^{y+3} - 3) + 3 = 2^{y+4} - 3$.

Exercise 7.8 ★★.

For each $n$, show that the function $y \mapsto A(n, y)$ is primitive recursive. Why does this not contradict Corollary 7.5?

Solution

By induction on $n$. $A(0, \cdot)$ is the successor. If $g = A(n, \cdot)$ is primitive recursive, then $A(n + 1, \cdot)$ satisfies $A(n + 1, 0) = g(1)$ and $A(n + 1, y + 1) = g(A(n + 1, y))$, a primitive recursion. Each row is primitive recursive, but each requires a derivation of its own, and the length of these derivations grows with $n$. A single derivation cannot handle all rows, which is what Corollary 7.5 says: the diagonal $n \mapsto A(n, n)$ uses rows of every level.

Exercise 7.9 ★★.

Show that the graph $G = \{(x, y, z) : A(x, y) = z\}$ of the Ackermann function is a primitive recursive predicate.

Hint

A computation of $A(x, y)$ can be recorded as a finite set of triples $(x', y', A(x', y'))$, all of whose values are bounded by $z$.

Solution

Call a finite set $T$ of triples closed if for each $(x', y', z') \in T$, the equations defining $A(x', y')$ are witnessed in $T$: if $x' = 0$ then $z' = y' + 1$; if $x' > 0$, $y' = 0$ then $(x' - 1, 1, z') \in T$; if $x', y' > 0$ then there is $w$ with $(x', y' - 1, w) \in T$ and $(x' - 1, w, z') \in T$. By induction along $<_{\mathrm{lex}}$, every triple in a closed set is in $G$; conversely, the set of triples occurring in the evaluation of $A(x, y)$ is closed and contains $(x, y, A(x, y))$. All triples occurring in that evaluation have components at most $z = A(x, y)$. Indeed, the evaluation of $A(x', y')$ only calls $A(x' - 1, 1)$, $A(x', y' - 1)$ and $A(x' - 1, A(x', y' - 1))$, whose values are at most $A(x', y')$ by the defining equations and Lemma 7.2; so all values $z'$ occurring are at most $z$. For a triple $(x', y', z')$, $y' < A(x', y') = z'$ by item 1, and $x' < A(0, y') + x' \leq A(x', y') = z'$ by item 4 applied $x'$ times. Coding $T$ as a sequence of triples without repetition, its length is at most $(z + 1)^3$ and its entries are codes of triples with components at most $z$, so the code is bounded by a primitive recursive function of $z$, and $G(x, y, z)$ holds iff there is a closed $T$ with code below this bound containing $(x, y, z)$: a bounded search over a primitive recursive predicate.

7.6 Notes and references

Ackermann’s original function had three arguments; the two-argument version used here is due to Péter, in the form given by Robinson. The majorization argument follows the standard textbook proof. The stratification of the primitive recursive functions by growth rate leads to the Grzegorczyk hierarchy.

• W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Mathematische Annalen 99 (1928), 118–133.
• R. Péter, Konstruktion nichtrekursiver Funktionen, Mathematische Annalen 111 (1935), 42–60.
• R. M. Robinson, Recursion and double recursion, Bulletin of the American Mathematical Society 54 (1948), 987–993.
• A. Grzegorczyk, Some classes of recursive functions, Rozprawy Matematyczne 4 (1953).