# computing the Ackermann function

## Primary tabs

\documentclass{article}
\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
%%\usepackage{xypic}
\usepackage{pst-plot}

% define commands here
\newcommand*{\abs}[1]{\left\lvert #1\right\rvert}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}}
\begin{document}
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:
\begin{eqnarray*}
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.
\end{eqnarray*}
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

\textbf{Definition}.  Suppose $z$ is in the range of $A$.  We say that a sequence $x_1,\ldots, x_n$ is an \emph{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}'$ can be formalized as follows:

\textbf{Definition}.  Suppose $\boldsymbol{x}$ is a finite non-empty sequence of non-negative integers.  A sequence $\boldsymbol{x}'$ is said to be \emph{immediately derivable} from $\boldsymbol{x}$, written $\boldsymbol{x}\longrightarrow \boldsymbol{x}'$, if exactly one of the following conditions holds:
\begin{enumerate}
\item $\boldsymbol{x}$ consists of one number, and $\boldsymbol{x}'=\boldsymbol{x}$;
\item $\boldsymbol{x}=\boldsymbol{y},0,z$, and $\boldsymbol{x}'=\boldsymbol{y},z+1$;
\item $\boldsymbol{x}=\boldsymbol{y},y,0$, with $y>0$, and $\boldsymbol{x}'=\boldsymbol{y},y-1,1$; or
\item $\boldsymbol{x}=\boldsymbol{y},y,z$, with $y>0$, $z>0$, and $\boldsymbol{x}'=\boldsymbol{y},y-1,y,z-1$,
\end{enumerate}
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}'$ to mean a finite chain of sequences
$$\boldsymbol{x}=\boldsymbol{x}_1, \boldsymbol{x}_2, \ldots, \boldsymbol{x}_m=\boldsymbol{x}'$$
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:
\begin{enumerate}
\item start with a sequence $x,y$, call the sequence \emph{derived at step} $k=0$;
\item If $\boldsymbol{x}$ is derived at step $k$, and $\boldsymbol{x}\longrightarrow \boldsymbol{x}'$, then $\boldsymbol{x}'$ is derived at step $k+1$.
\end{enumerate}
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:
\begin{itemize}
\item if $\boldsymbol{x}\longrightarrow \boldsymbol{x}'$, then $\boldsymbol{x}\ne \boldsymbol{x}'$ unless $\boldsymbol{x}$ consists of only one number.
\item if $\boldsymbol{x}\longrightarrow \boldsymbol{x}'$, then $\boldsymbol{x}$ is an Ackermann sequence for $z$ iff $\boldsymbol{x}'$ is.
\item if $\boldsymbol{x}\longrightarrow z$, where $z\in \mathbb{N}$, then $\boldsymbol{x}$ is an Ackermann sequence for $z$.
\item if $x>0$, then there is $t$ such that $x,y \Longrightarrow x-1,t$.
\item any pair $x,y$ is an Ackermann sequence for some $z$.
\end{itemize}
%%%%%
%%%%%
nd{document}