You are here
Homecomputing the Ackermann function
Primary tabs
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_{{n1}},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 nonempty sequence of nonnegative 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. $\boldsymbol{x}$ consists of one number, and $\boldsymbol{x}^{{\prime}}=\boldsymbol{x}$;
2. $\boldsymbol{x}=\boldsymbol{y},0,z$, and $\boldsymbol{x}^{{\prime}}=\boldsymbol{y},z+1$;
3. $\boldsymbol{x}=\boldsymbol{y},y,0$, with $y>0$, and $\boldsymbol{x}^{{\prime}}=\boldsymbol{y},y1,1$; or
4. $\boldsymbol{x}=\boldsymbol{y},y,z$, with $y>0$, $z>0$, and $\boldsymbol{x}^{{\prime}}=\boldsymbol{y},y1,y,z1$,
where $\boldsymbol{y}$ may be the empty sequence.
It is clear that conditions 24 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,m1$.
From the definition above, we can also describe the entire computational process rigorously:
1. start with a sequence $x,y$, call the sequence derived at step $k=0$;
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 x1,t$.

any pair $x,y$ is an Ackermann sequence for some $z$.
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