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.

The Ackermann function explained