# computing the Ackermann function

Recall that the Ackermann function  (the modern version) $A(x,y)$ is given by the following double recursive relation:

 $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)).$

From the equations above, we see that computing the Ackermann function involves first deciding whether the pair $(x,y)$ is such that

 $x=0,\qquad\mbox{or}\qquad x>0\mbox{ and }y=0,\qquad\mbox{or}\qquad x>0\mbox{ % and }y>0,$

which dictates which one of the three equations above to use. Let us illustrate this by a simple example: $x=1$ and $y=1$:

 $A(1,1)=A(0,A(1,0))=A(0,A(0,1))=A(0,2)=3.$

If $x=2$, then quite a few more steps are involved:

 $\displaystyle A(2,1)$ $\displaystyle=$ $\displaystyle A(1,A(2,0))=A(1,A(1,1))=A(1,A(0,A(1,0)))=A(1,A(0,A(0,1)))$ $\displaystyle=$ $\displaystyle A(1,A(0,2))=A(1,3)=A(0,A(1,2))=A(0,A(0,A(1,1)))$ $\displaystyle=$ $\displaystyle A(0,A(0,A(0,A(1,0))))=A(0,A(0,A(0,A(0,1))))$ $\displaystyle=$ $\displaystyle A(0,A(0,A(0,2)))=A(0,A(0,3))=A(0,4)=5.$

When $x>2$, computations of $A(x,y)$ becomes unwieldy, mainly due to the number of steps involved, and partially due to the number of $A$’s and the parentheses that need to be written down.

Nevertheless, based on the computations of $A(1,1)$ and $A(2,1)$ above, we see an algorithm  emerging for computing $A(x,y)$ in general. First, notice that in each of the expression $A(\ldots,)\ldots)$, the right parentheses all occur at the right end of the expression. Therefore, there is no ambiguity involved if the $A$’s and the parentheses were removed. Formalizing this notion, we have

Definition. Suppose $z$ is in the range of $A$. We say that a sequence $x_{1},\ldots,x_{n}$ is an Ackermann sequence for $z$ if

 $A(x_{1},A(x_{2},\ldots,A(x_{n-1},x_{n})\ldots)=z.$

In particular, the sequence $z$ of length $1$ is an Ackermann sequence for $z$.

Therefore, computing $A(x,y)=z$ is just a process of transforming the Ackermann sequence $x,y$ to the Ackermann sequence $z$, for $z$. Transforming one sequence $\boldsymbol{x}$ to another sequence $\boldsymbol{x}^{\prime}$ can be formalized as follows:

Definition. Suppose $\boldsymbol{x}$ is a finite non-empty sequence of non-negative integers. A sequence $\boldsymbol{x}^{\prime}$ is said to be immediately derivable from $\boldsymbol{x}$, written $\boldsymbol{x}\longrightarrow\boldsymbol{x}^{\prime}$, if exactly one of the following conditions holds:

1. 1.

$\boldsymbol{x}$ consists of one number, and $\boldsymbol{x}^{\prime}=\boldsymbol{x}$;

2. 2.

$\boldsymbol{x}=\boldsymbol{y},0,z$, and $\boldsymbol{x}^{\prime}=\boldsymbol{y},z+1$;

3. 3.

$\boldsymbol{x}=\boldsymbol{y},y,0$, with $y>0$, and $\boldsymbol{x}^{\prime}=\boldsymbol{y},y-1,1$; or

4. 4.

$\boldsymbol{x}=\boldsymbol{y},y,z$, with $y>0$, $z>0$, and $\boldsymbol{x}^{\prime}=\boldsymbol{y},y-1,y,z-1$,

where $\boldsymbol{y}$ may be the empty sequence.

It is clear that conditions 2-4 correspond to the three equations defining the Ackermann function.

We also write $\boldsymbol{x}\Longrightarrow\boldsymbol{x}^{\prime}$ to mean a finite chain of sequences

 $\boldsymbol{x}=\boldsymbol{x}_{1},\boldsymbol{x}_{2},\ldots,\boldsymbol{x}_{m}% =\boldsymbol{x}^{\prime}$

such that either $m=1$, or $m>1$, and $\boldsymbol{x}_{i}\rightarrow\boldsymbol{x}_{i+1}$ for $i=1,\ldots,m-1$.

From the definition above, we can also describe the entire computational process rigorously:

1. 1.

start with a sequence $x,y$, call the sequence derived at step $k=0$;

2. 2.

If $\boldsymbol{x}$ is derived at step $k$, and $\boldsymbol{x}\longrightarrow\boldsymbol{x}^{\prime}$, then $\boldsymbol{x}^{\prime}$ is derived at step $k+1$.

For example, the computation of $A(1,1)$ can be written simply as

 $1,1\longrightarrow 0,1,0\longrightarrow 0,0,1\longrightarrow 0,2% \longrightarrow 3\longrightarrow 3\longrightarrow\cdots$

A number of easy consequences of $\longrightarrow$ can now be listed:

• if $\boldsymbol{x}\longrightarrow\boldsymbol{x}^{\prime}$, then $\boldsymbol{x}\neq\boldsymbol{x}^{\prime}$ unless $\boldsymbol{x}$ consists of only one number.

• if $\boldsymbol{x}\longrightarrow\boldsymbol{x}^{\prime}$, then $\boldsymbol{x}$ is an Ackermann sequence for $z$ iff $\boldsymbol{x}^{\prime}$ is.

• if $\boldsymbol{x}\longrightarrow z$, where $z\in\mathbb{N}$, then $\boldsymbol{x}$ is an Ackermann sequence for $z$.

• if $x>0$, then there is $t$ such that $x,y\Longrightarrow x-1,t$.

• any pair $x,y$ is an Ackermann sequence for some $z$.

Title computing the Ackermann function ComputingTheAckermannFunction 2013-03-22 19:07:46 2013-03-22 19:07:46 CWoo (3771) CWoo (3771) 7 CWoo (3771) Algorithm msc 03D75