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.