You are here
HomeAckermann function is total recursive
Primary tabs
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,\qquad A(x+1,0)=A(x,1),\qquad 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. 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). 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:

$\operatorname{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$);

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

$\operatorname{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)_{{\operatorname{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},\ldots,r_{m})=p_{1}^{{r_{1}+1}}\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\longrightarrow\cdots\longrightarrow z\longrightarrow z\longrightarrow\cdots$ 
Let $s(x,y,i)$ denote the sequence at step $i$, then the above sequence can be rewritten:
$s(x,y,0)\longrightarrow s(x,y,1)\longrightarrow\cdots\longrightarrow s(x,y,k)\longrightarrow\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)=\langle x,y\rangle=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 $\langle x,y\rangle$ 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. 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 $\operatorname{lh}(n_{1})=1$, then $n_{2}=n_{1}$;
2. if $\operatorname{lh}(n_{1})>1$, and $(n_{1})_{{2}}=0$, then $n_{2}=h_{1}(n_{1})$, where
$h_{1}(n):=\operatorname{ext}(\operatorname{red}^{2}(n),(n)_{{1}}+1);$ 3. if $\operatorname{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):=\operatorname{ext}(\operatorname{ext}(\operatorname{red}^{2}(n),(n)_% {{2}}1),1);$ or
4. if $\operatorname{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):=\operatorname{ext}(\operatorname{ext}(\operatorname{ext}(% \operatorname{red}^{2}(n),(n)_{{2}}1),(n)_{{2}}),(n)_{{1}}1).$
If we define predicates:
1. $\Phi_{0}(n):=\operatorname{lh}(n)\leq 1$,
2. $\Phi_{1}(n):=\operatorname{lh}(n)>1\textrm{, and }(n)_{{2}}=0$,
3. $\Phi_{2}(n):=\operatorname{lh}(n)>1\textrm{, and }(n)_{{2}}>0\textrm{ and }(n% )_{{1}}=0$,
4. $\Phi_{3}(n):=\operatorname{lh}(n)>1\textrm{, and }(n)_{{2}}>0\textrm{ and }(n% )_{{1}}>0$.
Then each $\Phi_{i}$ is primitive recursive, pairwise exclusive, and $\Phi_{0}\equiv\neg\Phi_{1}\wedge\neg\Phi_{2}\wedge\neg\Phi_{3}$. Now, define $h$ as follows:
$h(n):=\left\{\begin{array}[]{ll}\operatorname{id}(n)&\textrm{if }\Phi_{0}(n),% \\ h_{1}(n)&\textrm{if }\Phi_{1}(n),\\ h_{2}(n)&\textrm{if }\Phi_{2}(n),\\ h_{3}(n)&\textrm{if }\Phi_{3}(n).\end{array}\right.$ 
Since $h$ is defined by cases, and each $h_{i}$ is primitive recursive, $h$ is also primitive recursive. ∎
Mathematics Subject Classification
03D75 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections