Ackermann function is total recursive
In this entry, we give a formal proof that the Ackermann function^{} $A(x,y)$, given by
$$A(0,y)=y+1,A(x+1,0)=A(x,1),A(x+1,y+1)=A(x,A(x+1,y))$$ 
is both a total function^{} and a recursive function^{}. Actually, the fact that $A$ is total is proved in this entry (http://planetmath.org/PropertiesOfAckermannFunction). It remains to show that $A$ is recursive.
Recall that the computation of $A(x,y)$, given $x,y$, can be thought of as an iterated operation^{} performed on finite sequences^{} of integers, starting with $x,y$ and ending with $z=A(x,y)$ (see this entry (http://planetmath.org/ComputingTheAckermannFunction)). It is this process we will utilize to prove that $A$ is recursive.
In the proof below, the following notations and definitions are used to simplify matters:

•
if $s$ is the sequence ${r}_{1},\mathrm{\dots},{r}_{m}$, then $E(s)$ or $\u27e8{r}_{1},\mathrm{\dots},{r}_{m}\u27e9$ denote the code number of $s$ given the encoding $E$;

•
$\mathrm{lh}(n)$ is the length of the sequence whose code number is $n$;

•
${(n)}_{i}$ is the $i$th number in the sequence whose code number is $n$;

•
${(n)}_{i}$ is the $i$th to the last number in the sequence whose code number is $n$ (so that ${(n)}_{1}$ is the last number in the sequence whose code number is $n$);

•
$\mathrm{red}(n)$ is the code number of the sequence obtained by deleting the last number of the sequence whose code number is $n$;

•
$\mathrm{ext}(n,a)$ is the code number of the sequence obtained by appending $a$ to the end of the sequence whose code number is $n$.
If $E$ is a primitive recursive encoding, then each of the above function is primitive recursive. For example, ${(n)}_{i}={(n)}_{\mathrm{lh}(n)\dot{}i+1}$.
Theorem 1.
$A$ is recursive.
Proof.
In this proof, the choice of encoding $E$ is the multiplicative encoding, for it is convenient and, more importantly, a primitive recursive encoding. Briefly,
$$E({r}_{1},\mathrm{\dots},{r}_{m})={p}_{1}^{{r}_{1}+1}\mathrm{\cdots}{p}_{m}^{{r}_{m}+1},$$ 
where ${p}_{i}$ is the $i$th prime number (so that ${p}_{1}=2$).
We know that computing $A(x,y)=z$ is basically a sequence of computations on finite sequences:
$$x,y\u27f6\mathrm{\cdots}\u27f6z\u27f6z\u27f6\mathrm{\cdots}$$ 
Let $s(x,y,i)$ denote the sequence at step $i$, then the above sequence can be rewritten:
$$s(x,y,0)\u27f6s(x,y,1)\u27f6\mathrm{\cdots}\u27f6s(x,y,k)\u27f6\mathrm{\cdots}$$ 
Define $f(x,y,i)=E(s(x,y,i))$. From this we see that
$$g(x,y)=\mu i[f(x,y,i)=f(x,y,i+1)].$$ 
is the function that computes the smallest number of steps needed so that the code number becomes stationary. When the code number is decoded, we get the resulting value of $A(x,y)$:
$$A(x,y)=D(f(x,y,g(x,y))),$$ 
where $D(m):={(m)}_{1}$, decodes $m$, and returns the last number in the sequence $s$ whose code number $E(s)$ is $m$.
Now the remaining task to show that $f$ is primitive recursive. First, note that
$$f(x,y,0)=\u27e8x,y\u27e9={2}^{x+1}{3}^{y+1}$$ 
is primitive recursive. Next, we want to express
$$f(x,y,n+1)=h(f(x,y,n)),$$ 
where $h$ is the function that changes the code number of the sequence $s(x,y,n)$ to the code number of the sequence $s(x,y,n+1)$. Once we obtain $h$ and show that $h$ is primitive recursive, then $f$ is primitive recursive, as it is defined by primitive recursion via primitive recursive functions $\u27e8x,y\u27e9$ and $h$.
To find out what $h$ is, recall the four rules of constructing the next sequence from the current one givne in this this entry (http://planetmath.org/ComputingTheAckermannFunction). Let ${n}_{1}=E(s(x,y,k))$ and ${n}_{2}=E(s(x,y,k+1))$. We rewrite the four rules using the notations and definitions here:

1.
if $\mathrm{lh}({n}_{1})=1$, then ${n}_{2}={n}_{1}$;

2.
if $\mathrm{lh}({n}_{1})>1$, and ${({n}_{1})}_{2}=0$, then ${n}_{2}={h}_{1}({n}_{1})$, where
$${h}_{1}(n):=\mathrm{ext}({\mathrm{red}}^{2}(n),{(n)}_{1}+1);$$ 
3.
if $\mathrm{lh}({n}_{1})>1$, and ${({n}_{1})}_{2}>0$ and ${({n}_{1})}_{1}=0$, then ${n}_{2}={h}_{2}({n}_{1})$, where
$${h}_{2}(n):=\mathrm{ext}(\mathrm{ext}({\mathrm{red}}^{2}(n),{(n)}_{2}1),1);$$ or

4.
if $\mathrm{lh}({n}_{1})>1$, and ${({n}_{1})}_{2}>0$ and ${({n}_{1})}_{1}>0$, then then ${n}_{2}={h}_{3}({n}_{1})$, where
$${h}_{3}(n):=\mathrm{ext}(\mathrm{ext}(\mathrm{ext}({\mathrm{red}}^{2}(n),{(n)}_{2}1),{(n)}_{2}),{(n)}_{1}1).$$
If we define predicates^{}:

1.
${\mathrm{\Phi}}_{0}(n):=\mathrm{lh}(n)\le 1$,

2.
${\mathrm{\Phi}}_{1}(n):=\mathrm{lh}(n)>1\text{, and}{(n)}_{2}=0$,

3.
${\mathrm{\Phi}}_{2}(n):=\mathrm{lh}(n)>1\text{, and}{(n)}_{2}0\text{and}{(n)}_{1}=0$,

4.
${\mathrm{\Phi}}_{3}(n):=\mathrm{lh}(n)>1\text{, and}{(n)}_{2}0\text{and}{(n)}_{1}0$.
Then each ${\mathrm{\Phi}}_{i}$ is primitive recursive, pairwise exclusive, and ${\mathrm{\Phi}}_{0}\equiv \mathrm{\neg}{\mathrm{\Phi}}_{1}\wedge \mathrm{\neg}{\mathrm{\Phi}}_{2}\wedge \mathrm{\neg}{\mathrm{\Phi}}_{3}$. Now, define $h$ as follows:
$$h(n):=\{\begin{array}{cc}\mathrm{id}(n)\hfill & \text{if}{\mathrm{\Phi}}_{0}(n),\hfill \\ {h}_{1}(n)\hfill & \text{if}{\mathrm{\Phi}}_{1}(n),\hfill \\ {h}_{2}(n)\hfill & \text{if}{\mathrm{\Phi}}_{2}(n),\hfill \\ {h}_{3}(n)\hfill & \text{if}{\mathrm{\Phi}}_{3}(n).\hfill \end{array}$$ 
Since $h$ is defined by cases, and each ${h}_{i}$ is primitive recursive, $h$ is also primitive recursive. ∎
Title  Ackermann function is total recursive 

Canonical name  AckermannFunctionIsTotalRecursive 
Date of creation  20130322 19:07:53 
Last modified on  20130322 19:07:53 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  15 
Author  CWoo (3771) 
Entry type  Theorem^{} 
Classification  msc 03D75 
Related topic  AckermannFunctionIsNotPrimitiveRecursive 