Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

1. Introduction

In this tutorial, we’ll discuss the Ackermann function and the problems associated with its computation.

We’ll first study its definition and calculate its output for small values of the input. Then, we’ll provide an analytical definition in terms of iterated exponentiation and its iteration.

At the end of this tutorial, we’ll know the definition of the Ackermann function and understand the reasons for its peculiar characteristics.

2. Definition of the Ackermann Function

The Ackermann function is generally indicated with \textbf{A}, and it’s a well-known binary function. Its two input terms can assume any non-negative integer value. The Ackermann function is thus defined:

Rendered by QuickLaTeX.com

This definition is straightforward in its essence. Surprisingly, though, it leads to fascinating and unexpected behavior as the input to the function grows.

3. The Ackermann Function for Small Input

The definition by itself may not be very informative to us: a good method for understanding this function is, therefore, to calculate some of its values. Here, we start from the lowest values of its input.

Let’s incrementally create a table that holds the values of \operatorname{A}(m,n), as m and n vary. The simplest case is m=0, where the function assumes the value of n+1:

Rendered by QuickLaTeX.com

The second simplest case is for \mathbf{n=0}, where the function assumes the value to the top-right of the corresponding cell. This is, intuitively, the meaning we assign to the second case of the definition in terms of the cells of our table.

We can precompute \operatorname{A}(m,n=1) for a few values of m, and then fill the first two columns accordingly. For simplicity, we’re now filling the table up to the fourth row, corresponding to m=3:

Rendered by QuickLaTeX.com

4. The Depth of the Recursion

For higher values of the input, computing the Ackermann function becomes increasingly harder. To see why this is the case, it makes sense to study how to compute the solution step-by-step for a relatively small input value.

Let’s look for example at the process of calculating \operatorname{A}(m=1,n=2). Because m>0 and n>0, we fall on the third case of the analytical definition. We, therefore, need to compute:

\operatorname{A}(1,2) = \operatorname{A}(0, \operatorname{A}(1,1))

The second term is a call to the function \operatorname{A} itself, that we need to resolve first. Because \operatorname{A}(1,1) falls again into the third case of the analytical definition, we need to replace it with \operatorname{A}(0, \operatorname{A}(1,0)):

\operatorname{A}(1,2) = \operatorname{A}(0, \operatorname{A}(0,\operatorname{A}(1,0)))

The rightmost operator has now a form that corresponds to the second case of the analytical definition. It therefore equates \operatorname{A}(0,1):

\operatorname{A}(1,2) = \operatorname{A}(0, \operatorname{A}(0,\operatorname{A}(0,1)))

Because the last operator now corresponds to the first case of the definition, we can replace it with its corresponding value \operatorname{A}(0,1) = 2:

\operatorname{A}(1,2) = \operatorname{A}(0, \operatorname{A}(0, 2))

The rightmost operator is also known to us, and it evaluates to \operatorname{A}(0, 2) =3:

\operatorname{A}(1,2) = \operatorname{A}(0, 3)

Finally, we apply again the definition for the first case and we can find the value for \operatorname{A}(0, 3) = 4, which we assign to the value of \operatorname{A}(1, 2) = 4. If we define the function as a program, all in all, to compute \textbf{A}\mathbf{(1, 2)}, we had to perform 6 calls to that function.

5. Down the Rabbit Hole

Note that the number of recursive calls to \operatorname{A} grows very fast. This is, in fact, the reason for the strange behavior that we observe from the fifth row of our table and onward. These are the values associated with \operatorname{A}(m,n) when m=4:

Rendered by QuickLaTeX.com

In the table above, the double arrow \uparrow\uparrow indicates the iterated exponentiation, expressed with Knuth’s notation. Notice that, from \operatorname{A}(4,2) onward, the function always evaluates to numbers so large that they can’t be easily written down. For every subsequent increment of m after m=4, we iterate the iterated exponentiation one more time:

Rendered by QuickLaTeX.com

Finally, because the recursion is significantly deep, the Ackermann function finds frequent usage as a metric for the performance of compilers. It’s also a good benchmark to test the efficient allocation of memory.

6. Conclusions

In this tutorial, we studied the Ackermann function and the problems associated with its computation.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!