# 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 (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},\ldots,r_{m}$, then $E(s)$ or $\langle r_{1},\ldots,r_{m}\rangle$ denote the code number of $s$ given the encoding $E$;

• $\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 (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. 1.

if $\operatorname{lh}(n_{1})=1$, then $n_{2}=n_{1}$;

2. 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. 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. 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. 1.

$\Phi_{0}(n):=\operatorname{lh}(n)\leq 1$,

2. 2.

$\Phi_{1}(n):=\operatorname{lh}(n)>1\textrm{, and }(n)_{-2}=0$,

3. 3.

$\Phi_{2}(n):=\operatorname{lh}(n)>1\textrm{, and }(n)_{-2}>0\textrm{ and }(n)_% {-1}=0$,

4. 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. ∎

Title Ackermann function is total recursive AckermannFunctionIsTotalRecursive 2013-03-22 19:07:53 2013-03-22 19:07:53 CWoo (3771) CWoo (3771) 15 CWoo (3771) Theorem msc 03D75 AckermannFunctionIsNotPrimitiveRecursive