Meaning and use of the Ackermann's function

[mathmari]

Hey!

Could you tell me which the meaning of the Ackermann's function is for the theoretical computer science?? (Wondering)

And which is its use?? (Wondering)

 

[Evgeny.Makarov]

Ackermann function is probably the simplest (and maybe historically first) example of a total function that is not primitive recursive, as your other thread discusses. It is also closely related to Knuth's up-arrow notation. The idea of this notation is very natural:

• addition is a repeated addition of 1
• multiplication is repeated addition
• exponentiation is repeated multiplication

This list can be continued by making the function at level $k+1$ to be repeated application of function at level $k$.

If $f$ is a function of two arguments. let $f\,x$ denote the function of one argument obtained from $f$ by fixing the first argument to $x$. This is often denoted by $f(x,\cdot)$. In general, if a function has $k$ argument and $i<k$, then the first $i$ arguments can be fixed to obtain function of the rest $k-i$ arguments. Similarly, if $\star$ is a binary operator, then $(x\star{})$ or $({}\star x)$ is a function of one argument obtained by fixing the first (respectively, the second) argument to $x$. This is called currying in computer science. If $g$ is a function of one argument, then $g^n$ is $n$-fold composition of $g$: $g^n(x)=g(g(\dots g(x)\dots))$ ($g$ is used $n$ times). Then the list of functions above can be written as follows.
\begin{align}
m+n&=(1+{})^n(m)&&\\
m\cdot n&=(m+{})^n(0)\\
m^n&=(m\cdot{})^n(1)
\end{align}
Knuth suggested extending this sequence by calling subsequent functions $\uparrow$, $\uparrow\uparrow=\uparrow^2$, $\uparrow\uparrow\uparrow=\uparrow^3$, …
\begin{align}
m\uparrow n=m^n&=(m\cdot{})^n(1)\\
m\uparrow^2 n&=(m\uparrow{})^n(1)\\
m\uparrow^3 n&=(m\uparrow^2{})^n(1)\\
\end{align}
and in general
\[
m\uparrow^{k+1}n=(m\uparrow^k{})^n(1)
\]
This can be extended to level 0 by $m\uparrow^0 n=mn$. The reason $\uparrow$ corresponds to exponentiation and not, say, to addition, is probably that $\uparrow$ looks like ^, which is used to type exponentiation in TeX. Also, the base case is different in addition and multiplication and becomes 1 only starting with exponentiation. However, we could define the function
\[
\operatorname{base}(k,m)=
\begin{cases}
m&k=-1\\
0&k=0\\
1&k>0
\end{cases}
\]
and then define
\begin{align}
m\uparrow^{-2} n&=n+1\\
m\uparrow^{k+1}n&=(m\uparrow^k{})^n(\operatorname{base}(k+1,m))&&k\ge-2
\end{align}
to extend the hierarchy to include successor, addition and multiplication.

Note that Ackermann function can be defined as
\begin{align}
A(0,n)&=n+1\\
A(k+1,n)&=(A\,k)^n(A(k,1))
\end{align}
From this it should be possible to prove, as Wikipedia claims, that
\[
A(k,n)=2\uparrow^{k-2} (n+3) - 3.
\]
So Ackermann function is not just some function defined by weird recursion, but is closely related to the hierarchy of addition, multiplication, exponentiation and so on.

It is interesting to meditate on the immensity of a number like $3\uparrow\uparrow\uparrow\uparrow4$, compared to which the number of particle in the universe is nothing. This is discussed in Knuth's book Things a Computer Scientist Rarely Talks About.

If one considers lambda calculus, then it can be shown that Ackermann function can be defined by recursion on type $\Bbb N\to\Bbb N$ (whereas primitive recursive functions are defined by recursion on $\Bbb N$). This shows that recursion on higher types is more powerful. In fact, functions defined by primitive recursion in all finite types are those about which first-order arithmetic can prove that they terminate. And even then there are total functions that cannot be defined by primitive recursion in all finite types: they provide an example of an arithmetic statement that is true, but not provable in arithmetic in the spirit of Gödel's incompleteness theorem.

I would recommend consulting the Wikipedia article, which seems pretty good, and links therein.

Edit: Switched $({}\uparrow^k m)^n(1)$ to $(m\uparrow^k{})^n(1)$ and similarly in other places. The previous version was incorrect. Thus, $({}\uparrow m)^n(1)=1$, but $(m\uparrow{})^n(1)={m_{{}}^{{m^{{{}^{{.\,^{{.\,^{{.\,^{m}}}}}}}}}}}}$.