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,A(x+1,0)=A(x,1),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,\text{or}\mathit{\hspace{1em}\hspace{1em}}x>0\text{and}y=0,\text{or}\mathit{\hspace{1em}\hspace{1em}}x0\text{and}y0,$$ 
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:
$A(2,1)$  $=$  $A(1,A(2,0))=A(1,A(1,1))=A(1,A(0,A(1,0)))=A(1,A(0,A(0,1)))$  
$=$  $A(1,A(0,2))=A(1,3)=A(0,A(1,2))=A(0,A(0,A(1,1)))$  
$=$  $A(0,A(0,A(0,A(1,0))))=A(0,A(0,A(0,A(0,1))))$  
$=$  $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(\mathrm{\dots},)\mathrm{\dots})$, 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},\mathrm{\dots},{x}_{n}$ is an Ackermann sequence for $z$ if
$$A({x}_{1},A({x}_{2},\mathrm{\dots},A({x}_{n1},{x}_{n})\mathrm{\dots})=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 $\bm{x}$ to another sequence ${\bm{x}}^{\prime}$ can be formalized as follows:
Definition. Suppose $\bm{x}$ is a finite nonempty sequence of nonnegative integers. A sequence ${\bm{x}}^{\prime}$ is said to be immediately derivable from $\bm{x}$, written $\bm{x}\u27f6{\bm{x}}^{\prime}$, if exactly one of the following conditions holds:

1.
$\bm{x}$ consists of one number, and ${\bm{x}}^{\prime}=\bm{x}$;

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

3.
$\bm{x}=\bm{y},y,0$, with $y>0$, and ${\bm{x}}^{\prime}=\bm{y},y1,1$; or

4.
$\bm{x}=\bm{y},y,z$, with $y>0$, $z>0$, and ${\bm{x}}^{\prime}=\bm{y},y1,y,z1$,
where $\bm{y}$ may be the empty sequence.
It is clear that conditions 24 correspond to the three equations defining the Ackermann function.
We also write $\bm{x}\u27f9{\bm{x}}^{\prime}$ to mean a finite chain of sequences
$$\bm{x}={\bm{x}}_{1},{\bm{x}}_{2},\mathrm{\dots},{\bm{x}}_{m}={\bm{x}}^{\prime}$$ 
such that either $m=1$, or $m>1$, and ${\bm{x}}_{i}\to {\bm{x}}_{i+1}$ for $i=1,\mathrm{\dots},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 $\bm{x}$ is derived at step $k$, and $\bm{x}\u27f6{\bm{x}}^{\prime}$, then ${\bm{x}}^{\prime}$ is derived at step $k+1$.
For example, the computation of $A(1,1)$ can be written simply as
$$1,1\u27f60,1,0\u27f60,0,1\u27f60,2\u27f63\u27f63\u27f6\mathrm{\cdots}$$ 
A number of easy consequences of $\u27f6$ can now be listed:

•
if $\bm{x}\u27f6{\bm{x}}^{\prime}$, then $\bm{x}\ne {\bm{x}}^{\prime}$ unless $\bm{x}$ consists of only one number.

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

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

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

•
any pair $x,y$ is an Ackermann sequence for some $z$.
Title  computing the Ackermann function 

Canonical name  ComputingTheAckermannFunction 
Date of creation  20130322 19:07:46 
Last modified on  20130322 19:07:46 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Algorithm 
Classification  msc 03D75 