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,A(x+1,0)=A(x,1),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 ($\mathrm{dom}(A)={\mathbb{N}}^{2}$).

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

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

4.
$$.

5.
$$.

6.
$A(x,y+1)\le A(x+1,y)$.

7.
$$.

8.
$$

9.
For any $r,s$, $$ 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 welldefined, so $(0,y)\in \mathrm{dom}(A)$ for all $y$. Next, suppose that for a given $x$, $(x,y)\in \mathrm{dom}(A)$ for all $y$. We want to show that $(x+1,y)\in \mathrm{dom}(A)$ for all $y$. To do this, induct on $y$. First, $(x+1,0)\in \mathrm{dom}(A)$, since $A(x+1,0)=A(x,1)$ is welldefined. Next, assume that $(x+1,y)\in \mathrm{dom}(A)$. Then $A(x,A(x+1,y))=A(x+1,y+1)$ is welldefined. so $(x+1,y+1)\in \mathrm{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, $$. Next, assume $$, where $x>0$. Then $$.

5.
Induct on $x$. First, $$. Next, assume that $$. Then $$.

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

7.
Induct on $x$. First, $$. Next, assume that $$. There are two cases: $y=0$. Then $$. Otherwise, $y=z+1$, so that $$.

8.
$$.

9.
Let $z=\mathrm{max}\{r,s\}$. Then $$. 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}\mathrm{:}\mathrm{N}\mathrm{\to}\mathrm{N}$ by ${A}_{n}\mathit{}\mathrm{(}m\mathrm{)}\mathrm{=}A\mathit{}\mathrm{(}n\mathrm{,}m\mathrm{)}$. 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 ${\mathrm{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  20130322 19:07:25 
Last modified on  20130322 19:07:25 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  9 
Author  CWoo (3771) 
Entry type  Result 
Classification  msc 03D75 