The Ackermann function explained

The Ackermann function is a recursive function originally invented by Wilhelm Ackermann. It is one of a series of mathematical functions that quickly generates enormous numbers. If you haven't read my article on Knuth's up arrow notation, I recommend taking a look at it first before reading about this function.

Introduction

The Ackermann function is famous for being one of the simplest and earliest discovered examples of a total computable function that isn't primitive recursive. In laymen terms, this means that we can write a program that could execute this function but we couldn't use only do-loops. We would need to use a combination of for-loops and do-loops.

This function is also wickedly powerful and capable of generating very large numbers very quickly.

XKCD also had a comic reference the Ackermann function:

Definition

There are three main rules for the Ackermann function. It is defined as follows:

\( A(m,n) = \)

  • \( n+1 \text{ if } m=0 \),
  • \( A(m-1,1) \text{ if } n=0 \), or
  • \( A(m-1,A(m,n-1)) \) otherwise.

Let's take a look at a few expansions to see how the function works:

\(A(1,2) \)
\(= A(0,A(1,1)) \)
\(= A(0,A(0,A(1,0))) \)
\(= A(0,A(0,A(0,1))) \)
\(= A(0,A(0,2)) \)
\(= A(0,3) \)
\(= 4 \)

Here is another example:

\(A(4,3) = A(3,A(4,2)) \)
\(= A(3,A(3,A(4,1))) \)
\(= A(3,A(3,A(3,A(4,0)))) \)
\(= A(3,A(3,A(3,A(3,1)))) \)
\(= A(3,A(3,A(3,A(2,A(3,0))))) \)
\(= A(3,A(3,A(3,A(2,A(2,1))))) \)
\(= A(3,A(3,A(3,A(2,A(1,A(2,0)))))) \)
\(= A(3,A(3,A(3,A(2,A(1,A(1,1)))))) \)
\(= A(3,A(3,A(3,A(2,A(1,A(0,A(1,0))))))) \)
\(= A(3,A(3,A(3,A(2,A(1,A(0,A(0,1))))))) \)
\(= A(3,A(3,A(3,A(2,A(1,A(0,2)))))) \)
\(= A(3,A(3,A(3,A(2,A(1,3))))) \)
\(= ...\)

Eventually the example will get to this:

\(A(3,2^{65536}-3) \)
\(= ...\)

and it will finally reach this:

\(= 2^{2^{65536}}-3 \)

This table shows you how quickly this function grows:

m/n 0 1 2 3 n
0 1 2 3 4 \( n+1 \)
1 2 3 4 5 \(n+2 \\ = 2+(n+3)-3\)
2 3 5 7 9 \(2n+3 \\ = 2 \cdot (n+3) - 3\)
3 5 13 29 61 \(2^{n+3} - 3\)
4 \( 13 = 2^{2^2} - 3 \) \( 65533 \\ = 2^{2^{2^2}} - 3 \) \( 2^{65533} - 3 \\ = 2^{2^{2^{2^2}}} - 3 \) \( 2^{2^{65533}} - 3 \\ = 2^{2^{2^{2^{2^2}}}} - 3 \) \(\underbrace{2^{2^{2^{\unicode{x22f0}}}}}_{n+3} - 3\)
5 \( 2\uparrow\uparrow\uparrow3 - 3 \) \( 2\uparrow\uparrow\uparrow4-3\) \( 2\uparrow\uparrow\uparrow5-3 \) \( 2\uparrow\uparrow\uparrow6 -3 \) \( 2\uparrow\uparrow\uparrow(n+3)-3 \)

Notice how quickly the Ackermann function grows? Another way to visualize the growth of the Ackermann function is to see it represented in Knuth's up arrow notation:

\(1\uparrow1\)
\(2\uparrow\uparrow2\)
\(3\uparrow\uparrow\uparrow3\)
\(4\uparrow\uparrow\uparrow\uparrow4\)
\(5\uparrow\uparrow\uparrow\uparrow\uparrow5\)
\(6\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow6\)
\(7\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow7\)

We can also express Graham's number with the Ackermann function:

$$ G = A^{64}(4) $$

The \( A^{64} \) means we need to run the Ackermann function 64 times using the results of each previous iteration as input for the next: \( A(A(A...A(4))) \) with 64 A's.

On the Fast Growing Hierarchy which ranks the strength of various fast growing functions, the Ackermann function would be:

$$ A(n,n) \approx f_{\omega}(n) $$

The Ackermann function is pretty cool. For more fast growing functions you might want to check out my article on Knuth's up arrow notation.