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.