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.

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

Title	Ackermann function is total recursive
Canonical name	AckermannFunctionIsTotalRecursive
Date of creation	2013-03-22 19:07:53
Last modified on	2013-03-22 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