properties of Ackermann function

In this entry, we derive some basic properties of the Ackermann function $A(x,y)$ , defined by double recursion, as follows:

A(0,y)=y+1,\quad A(x+1,0)=A(x,1),\quad A(x+1,y+1)=A(x,A(x+1,y)).

These properties will be useful in proving that $A$ is not primitive recursive.

1.

$A$ is total ( $\operatorname{dom}(A)=\mathbb{N}^{2}$ ).
2.

$A(1,y)=y+2$ .
3.

$A(2,y)=2y+3$ .
4.

$y<A(x,y)$ .
5.

$A(x,y)<A(x,y+1)$ .
6.

$A(x,y+1)\leq A(x+1,y)$ .
7.

$A(x,y)<A(x+1,y)$ .
8.

$A(r,A(s,y))<A(r+s+2,y)$
9.

For any $r, s$ , $A(r,y)+A(s,y)<A(t,y)$ for some $t$ not depending on $y$ .

Most of the proofs are done by induction.

Proof.

1.

Induct on $x$ . First, $A(0,y)=y+1$ is well-defined, so $(0,y)\in\operatorname{dom}(A)$ for all $y$ . Next, suppose that for a given $x$ , $(x,y)\in\operatorname{dom}(A)$ for all $y$ . We want to show that $(x+1,y)\in\operatorname{dom}(A)$ for all $y$ . To do this, induct on $y$ . First, $(x+1,0)\in\operatorname{dom}(A)$ , since $A(x+1,0)=A(x,1)$ is well-defined. Next, assume that $(x+1,y)\in\operatorname{dom}(A)$ . Then $A(x,A(x+1,y))=A(x+1,y+1)$ is well-defined. so $(x+1,y+1)\in\operatorname{dom}(A)$ as well.
2.

Induct on $y$ . First, $A(1,0)=A(0,1)=2$ . Next, assume $A(1,y)=y+2$ . Then $A(1,y+1)=A(0,y+2)=y+3=(y+1)+2$ .
3.

Induct on $y$ . First, $A(2,0)=A(1,1)=1+2=3$ . Next, assume $A(2,y)=2y+3$ . Then $A(2,y+1)=A(1,A(2,y))=A(2,y)+2=(2y+3)+2=2(y+1)+3$ .
4.

Induct on $x$ . First, $y<y+1=A(0,y)$ . Next, assume $y<A(x,y)$ , where $x>0$ . Then $y+1\leq A(x,y)<A(x-1,A(x,y))=A(x,y+1)$ .
5.

Induct on $x$ . First, $A(0,y)=y+1<y+2=A(0,y+1)$ . Next, assume that $A(x,y)<A(x,y+1)$ . Then $A(x+1,y)<A(x,A(x+1,y))=A(x+1,y+1)$ .
6.

Induct on $y$ . First, $A(x,1)=A(x+1,0)$ . Next, assume that $A(x,y+1)\leq A(x+1,y)$ . Then $A(x,y+2)\leq A(x,A(x,y+1))\leq A(x,A(x+1,y))=A(x+1,y+1)$ .
7.

Induct on $x$ . First, $A(0,y)=y+1<y+2=A(1,y)$ . Next, assume that $A(x,y)<A(x+1,y)$ . There are two cases: $y=0$ . Then $A(x+1,0)=A(x,1)<A(x+1,1)$ . Otherwise, $y=z+1$ , so that $A(x+1,y)=A(x+1,z+1)=A(x,A(x+1,z))\leq A(x,A(x,z+1))=A(x,A(x,y))<A(x,A(x+1,y))=% A(x+1,y+1)$ .
8.

$A(r,A(s,y))<A(r+s,A(s,y))<A(r+s,A(r+s+1,y))=A(r+s+1,y+1)\leq A(r+s+2,y)$ .
9.

Let $z=\max\{r,s\}$ . Then $A(r,y)+A(s,y)\leq 2A(z,y)<2A(z,y)+3=A(2,A(z,y))<A(4+z,y)$ . The proof is completed by setting $t=4+z$ .

∎

With respect to the recursive property of $A$ , we see that $A$ is recursive, since, by Church’s Thesis, $A$ can be effectively computed (in fact, a program can be easily written to compute $A(x,y)$ ). We also have the following:

Proposition 1.

Define $A_{n}:\mathbb{N}\to\mathbb{N}$ by $A_{n}(m)=A(n,m)$ . Then $A_{n}$ is primitive recursive for each $n$ .

Proof.

$A_{0}(m)=m+1=s(m)$ , so is primitive recursive. Now, assume $A_{n}$ is primitive recursive, then $A_{n+1}(0)=A(n+1,0)=A(n,1)=A_{n}(1)=k$ , and $A_{n+1}(m+1)=A(n+1,m+1)=A(n,A(n+1,m))=A_{n}(A(n+1,m))=A_{n}(A_{n+1}(m))$ , so that $A_{n+1}$ is defined by primitive recursion via the constant function $\operatorname{const}_{k}$ , and $A_{n}$ , which is primitive recursive by the induction hypothesis. Therefore $A_{n+1}$ is primitive recursive also. ∎

The most important fact about $A$ concerning recursiveness is that $A$ is not primitive recursive. Due to the length of its proof, it is demonstrated in this entry (http://planetmath.org/AckermannFunctionIsNotPrimitiveRecursive).

Title	properties of Ackermann function
Canonical name	PropertiesOfAckermannFunction
Date of creation	2013-03-22 19:07:25
Last modified on	2013-03-22 19:07:25
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	9
Author	CWoo (3771)
Entry type	Result
Classification	msc 03D75