Ackermann’s function

Ackermann’s function#

The most famous example of a function which is computable and total but not primitive recursive is Ackermann’s function. It is given by

\[\begin{split} A(x,y)\quadeq \left\{ \begin{array}{ll} y+1 &\mbox{if $x=0$} \\ A(x-1,1) & \mbox{if $x\neq 0$ and $y=0$}\\ A(x-1,A(x,y-1)) & \mbox{otherwise} \end{array} \right. \end{split}\]

This section shows that $A$ is not primitive recursive.

Buck’s function#

We want to mention a different function that is also total and computable, Buck’s function $F(m,n)$. We then will give the full details on why it is not primitive recursive. Here is Buck’s function $F(m,n)$.

\[\begin{split} \begin{array}{lcl} F(m,0) & = & m+1 \\ \\ F(0,n) & = & \left\{ \begin{array}{ll} 2 &\mbox{if $n = 1$} \\ 0 &\mbox{if $n = 2$} \\ 1 &\mbox{if $n \geq 3$} \end{array} \right.\\ \\ F(m+1,n+1) & = & F(F(m,n+1), n)\\ \end{array} \end{split}\]

Here are some special cases. The reason for moving from $A$ to $F$ is just that the expressions below are a little more elegant than what we get with $A$. But the two functions are closely related, as we’ll see below.

\[\begin{split} \begin{array}{lcl} F(m,1) & = &2+ m\\ F(m,2) & = & 2\cdot m \\ F(m,3) & = & 2^m \\ F(m,4) & = & 2^{2^{\rddots2}}\mbox{, this is a tower of $m$ 2's} \end{array} \end{split}\]

Here also is a table of values of this function for small $m$ (the row) and $n$ (the column).

\[\begin{split} \begin{array}{|c||c|c|c|c|c|c|} \hline & 0 & 1 & 2 & 3 & 4 \\ \hline % \diagbox[width=\dimexpr \textwidth/8+2\tabcolsep\relax, height=1cm]{$ u$}{$v$} & 0 & 1 & 2 & 3 & 4 \\ % \diagbox{$m$}{$n$} & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & 1 & 2 & 0 & 1 & 1 & 1\\ \hline 1 & 2 & 3 & 2 & 2 & 2 & 2 \\ \hline 2 & 3 & 4 & 4 & 4 & 4 & 4\\ \hline 3 & 4 & 5 & 6 & 8 & 16 & 2^{16}=65,536 \\ \hline 4 & 5 & 6 & 8 & 16 & 2^{16}=65,536 & F(2^{16},4)\\ \hline 5 & 6 & 7 & 10 & 32 & 2^{2^{16}} & F(F(4,5),4) \\ \hline \end{array} \end{split}\]

Lemma 3

For $n\geq 3$ and all $a$, $a < F(a,n)$.

Proof. For $n = 3$, it’s clear: $a < 2^a = F(a,3)$.
Assume our result for $n\geq 3$, we check it for $n +1$. We argue by induction on $a$.
First, $0 < 1 = F(0,n+1)$.
Assuming that $a < F(a,n+1)$, we have

\[\begin{split} \begin{array}{lcll} a & < & F(a,n+1) &\mbox{induction hypothesis on $a$}\\ & < & F(F(a,n+1), n) &\mbox{induction hypothesis on $n$}\\ & = & F(a+1, n+1) \end{array} \end{split}\]

The calculation above has two strict inequalities, and it implies that $a+1 < F(a+1, n+1)$.

Lemma 4

If $n \geq 0$ and $a < b$, then $F(a,n) < F(b,n)$.

Proof. By induction on $n$.

For $n = 0$, $F(a,0) = a+1 < b+1 = F(b,0)$.

Similar reasoning applies with $n = 1$ and $n = 2$.

Assuming our result for $n\geq 2$, we argue by induction on $b$ that for $a < b$, $F(a, n+1) < F(b, n+1)$. We need only show that $F(a,n+1) < F(a+1, n+1)$. But

\[\begin{split} \begin{array}{lcll} F(a,n+1) & < & F(F(a,n+1),n) \\ & = & F(a+1, n+1) \end{array} \end{split}\]

In the first step, we used Lemma 3 and the fact that $n + 1 \geq 3$.

Lemma 5

$3 \leq F(2, v)\leq F(2, v+1)$.
If $u \geq 3$, then $3 \leq F(u,v) < F(u,v+1)$.

Proof. We show both parts together by induction on $v$. For $v = 0$: $F(2,0) = 3 < 4 = F(2,1)$, and for all $u$, $F(u,0) = u+1 < u+2 = F(u,1)$.

Assume both parts for $v$; we check both for $v +1$. For (1), see the chart. For (2) we use induction on $u \geq 3$.
First, a calculation for $u\geq 2$:

\[\begin{split} \begin{array}{lcll} F(u+1,v+1) & = & F(F(u,v+1),v) \\ & < & F(F(u,v+1),v+1) & \mbox{($*$)} \\ & \leq & F(F(u,v+2),v+1) & \mbox{($**$)} \\ & = & F(u+1, v+2) \end{array} \end{split}\]

When $u = 2$, step ($*$) is by the induction hypothesis on $v$; we also used $3 < F(3, v+1)$, and this is due to point (1). We have equality in the step ($**$). From above, $ F(3,v+1) < F(3, v+2) $. We have the base case, except for the point that $3 \leq F(3,v+1)$, and we verify this below.

For the induction step on $u$, we assume about $u$ that $ 3 \leq F(u,v+1) < F(u, v+2) $. We repeat the calculation above. Step ($*$) follows from the induction hypothesis on $v$, and step ($**$) from Lemma 4. To complete the verification of (2), both for the base case $u = 3$ and the induction step on $u$, we need only check that $F(F(u,v+1),v) \geq 3$. Let $k = F(u, v+1)$. Then $k \geq 3$ since $u \geq 2$, and $F(k,v) \geq 3$ by induction hypothesis on $v$.

Lemma 6

For all $x\geq 3$ and $n\geq 2$, $F(F(x,n), n) < F(x, n+2)$.

Proof. By induction on $n\geq 2$. For $n=2$ and $x = 3$, $F(F(3,2), 2) = 12 < 16 = F(3, 4)$. For $n=2$ and $x = 4$, $F(F(4,2), 2) = 16 < 2^{16} = F(3, 5)$. For $n = 2$ and $x\geq 5$, $F(F(x,2),2) = 4x < 2^x = F(x,3) < F(x,4)$.

Assume about $n\geq 2$ that for all $x\geq 3$, $F(F(x,n), n) < F(x, n+2)$. Then

\[\begin{split} \begin{array}{lcll} F(F(x+1, n), n) & = &F( F(F(x,n), n-1), n) \\ & < & F( F(F(x,n), n), n) \\ & < & F( F(x, n+2), n) &\mbox{induction hypothesis}\\ & < & F( F(x, n+2), n+1) \\ & = & F(x+1, n+2)\\ \end{array} \end{split}\]

In these calculuations, we used Lemma 5 twice, using also that $F(x,n+2)\geq F(x,n)\geq 3$.

Lemma 7

For all $x\geq 3$ and $n,m\geq 2$, $F(F(x,n), m) < F(x, n+m)$.

Proof. Let $p = \max\{m,n\}$. Using Lemma 5 and Lemma 6,

\[ F(F(x,n), m) < F(F(x,p),p) < F(x, p+2) \leq F(x, n+m). \]

Lemma 8

For every primitive recursive $f:N^k \to N$, there is some $r \geq 3$ so that for all $\overline{x} = x_1,\ldots, x_k\in N^k$, $ f(\overline{x}) < F(\hat{x}_i, r)$.

Proof. By induction on $f$. For the constant $0$ function, successor function $s(x) = x+1$, and projections $pr^n_k(x_1,\ldots, x_k) = x_n$, we take $r = 3$. For example, $pr^n_k(\bar{x}) = x_n \leq \hat{x} < F(\hat{x}, 3)$ by Lemma 3.

Suppose that $f: N^k \to N$ is given by

\[ f(\bar{x}) = h(g_1(\bar{x}), \ldots, g_{\ell}(\bar{x})) \]

where $h: N^{\ell} \to N$, and $g_i: N^k \to N$ for $1\leq i \leq \ell$. Let $s\geq 3$ be such that $h(\bar{y}) < F(\hat{y}, s)$ for all $\bar{y} \in N^{\ell}$, and for each $i$, let $r_i\geq 3$ be such that $g_i(\bar{y}) < F(\hat{x}, r_i)$ for all $\bar{x} \in N^{k}$.

Let $\bar{x} \in N^{k}$. Let $z_1 = g_1(\bar{x})$, $\ldots$, $z_{\ell} = g_{\ell}(\bar{x})$. Then $\hat{z} = \max\{z_1, \ldots, z_{\ell},3\}$. For each $j<\ell$, $z_j < F(\hat{x},r_j)$. Thus $\hat{z} < \max_j F(\hat{x},r_j)$.

\[\begin{split} \begin{array}{lclll} f(\bar{x}) &= & h(g_1(\bar{x}), \ldots, g_{\ell}(\bar{x})) \\ &< & F(\hat{z}, s) &\mbox{by definition of $s$, using $g_j(\bar{x})\geq 3$} \\ & < & F(\max_j F(\hat{x}, r_j), s) & \mbox{(2)}\\ & \leq & F( F(\hat{x}, \max_j r_j) , s)& \mbox{(3)}\\ & < & F(\hat{x}, \max_j r_j + s) & \mbox{(4)}\\ \end{array} \end{split}\]

Point (2) uses Lemma 4, (3) uses Lemma 5 and $\hat{x} \geq 3$, and (4) uses Lemma 7 and $\hat{x} \geq 3$, $r_1 \geq 2$.

We have used Lemma 4 at other several points. To conclude this step of the induction, we have shown that the number $ \max_j r_j + s$ has the required property for $f$.

Suppose that $f(\bar{x},y)$ is defined by primitive recursion from $h(\bar{x})$ and $k(\bar{x},y,z)$ as: $f(\bar{x},0) = h(\bar{x})$, and $f(\bar{x},y+1) = k(\bar{x}, y, f(\bar{x},y))$. Let $r$ and $s$ be such that $h(\bar{x}) < F(\hat{x}, r)$ and $k(\bar{x}, y,z) < F(\max(\hat{x}, y, z), s)$.

Let $t = 1+ \max(r,s)$.

We introduce some notation for readability. Let $p = \max(\hat{x},y)= (\bar{x},y)^{\widehat{}}$, and let $q = \max(p,f(\bar{x}, y) )$. We show that $t+2$ has the desired property: for all $\bar{x}, y$, $f(\bar{x},y) < F(p, t+2)$.

First we have a preliminary claim:

$f(\bar{x}, y) < F(\hat{x} + y, t)$ for all $\bar{x}$ and all $y\geq 0$.

The proof is by induction on $y$. This is clear for $y=0$. Assume about $y$ that $f(\bar{x}, y) < F(\hat{x} + y, t)$. By Lemma 3, $\hat{x}$ and $y$ are also $< F(\hat{x}+y,t)$, since $t\geq 3$. Thus $q < F(\hat{x} +y, t)$. So

\[\begin{split} \begin{array}{lclll} f(\bar{x},y+1) & = & k(\bar{x}, y, f(\bar{x},y)) \\ & < & F(q,s) &\mbox{by definition of $s$} \\ & < & F(F(\hat{x} + y, t), s) & \mbox{(4)}\\ & \leq & F(F(\hat{x} + y, t), t-1) &\mbox{since $s\leq t-1$}\\ & = & F(\hat{x} + y + 1, t) &\mbox{by definition of $F$} \end{array} \end{split}\]

Point (4) uses Lemma 4.

Our claim proved, we now fix $\bar{x},y$. We have

\[\begin{split} \begin{array}{lclll} f(\bar{x},y) & < & F(\hat{x} + y, t) &\mbox{by our claim above}\\ & \leq & F(2p, t) &\mbox{by definition of $p$} \\ & = & F(F(p,2), t) &\mbox{since $F(m,2) = 2m$} \\ & = & F(p, t+2) &\mbox{(5)}\\ % & = & F(F(p+1,2), t+1) & \mbox{since $F(m,2) = 2m$} \\ % & < & F(p+1,t+2) &\mbox{(6)}\\ % & = & F(\hat{x} + (y+1), t+2) &\\ \end{array} \end{split}\]

Point (5) uses Lemma 7 and the fact that $p\geq 3$ and $t \geq 3$. (6) uses Lemma 4.

This completes the induction step for primitive recursion, hence the lemma overall.

Theorem 8

Buck’s function $F$ is not primitive recursive.

Proof. Suppose towards a contradiction that $F$ were primitive recursive. By Lemma 8, let $r\geq 3$ be such that $F(x,y) < F(\{x,y\}^{\widehat{}}, r)$ for all $x,y$. Take $x = y = r$. Then $\{x,y\}^{\widehat{}} = r$. We have $F(r,r) <F(r,r)$, and this is the contradiction.

Back to Ackermann’s function#

We can use our work on Buck’s function to see that Ackermann’s function is not primitive recursive.

Exercise 63

Buck showed that

\[\begin{split} A(m,n) = \left\{ \begin{array}{ll} n+1 & \mbox{if $m = 0$}\\ F(m, n+3)-3 &\mbox{if $m>0$} \end{array} \right. \end{split}\]

Use this and Theorem 8 to show that $A$ is not primitive recursive.

Credits

Buck’s function comes from his paper

R. C. Buck, Mathematical Induction and Recursive Definitions. The American Mathematical Monthly, Vol. 70, No. 2 (Feb., 1963), pp. 128-135.

The first (?) proof that Ackermann’s function is total but not primitive recursive was given in the paper (in German)

Rózsa Péter, (1935). “Konstruktion nichtrekursiver Funktionen”. Mathematische Annalen. 111: 42–60.

Péter went on to write the first book on primitive recursive functions, translated into English as

Rózsa Péter, (1967). Recursive Functions (3d revised ed.). Academic Press.

Ackermann’s function

Contents

Ackermann’s function#

Buck’s function#

Back to Ackermann’s function#