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}}x>0\text{ 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:

$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_{n-1},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 $𝒙$ to another sequence ${𝒙}^{\prime }$ can be formalized as follows:

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

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

2. $𝒙=𝒚,0,z$, and ${𝒙}^{\prime }=𝒚,z+1$;

3. $𝒙=𝒚,y,0$, with $y>0$, and ${𝒙}^{\prime }=𝒚,y-1,1$; or

4. $𝒙=𝒚,y,z$, with $y>0$, $z>0$, and ${𝒙}^{\prime }=𝒚,y-1,y,z-1$,

where $𝒚$ may be the empty sequence.

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

We also write $𝒙⟹{𝒙}^{\prime }$ to mean a finite chain of sequences

$$𝒙={𝒙}_1,{𝒙}_2,\mathrm{\dots },{𝒙}_m={𝒙}^{\prime }$$

such that either $m=1$, or $m>1$, and ${𝒙}_i\to {𝒙}_{i+1}$ for $i=1,\mathrm{\dots },m-1$.

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 $𝒙$ is derived at step $k$, and $𝒙⟶{𝒙}^{\prime }$, then ${𝒙}^{\prime }$ is derived at step $k+1$.

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

$$1,1⟶0,1,0⟶0,0,1⟶0,2⟶3⟶3⟶\mathrm{\cdots }$$

A number of easy consequences of $⟶$ can now be listed:

• if $𝒙⟶{𝒙}^{\prime }$, then $𝒙\ne {𝒙}^{\prime }$ unless $𝒙$ consists of only one number.

• if $𝒙⟶{𝒙}^{\prime }$, then $𝒙$ is an Ackermann sequence for $z$ iff ${𝒙}^{\prime }$ is.

• if $𝒙⟶z$, where $z\in \mathbb{N}$, then $𝒙$ is an Ackermann sequence for $z$.

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

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

Title	computing the Ackermann function
Canonical name	ComputingTheAckermannFunction
Date of creation	2013-03-22 19:07:46
Last modified on	2013-03-22 19:07:46
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	7
Author	CWoo (3771)
Entry type	Algorithm
Classification	msc 03D75