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.