Yesterday I came in touch with a curious, astonishing mathematical function. It's called Ackermann function.

Mathematically speaking, it is a **well-defined total function**. That is, it has defined values for every integer input (= total function), and this value is not ambiguous (every input has one and one only possible output value) (= well-defined).

Speaking about computer science, this function is **computable**, but it's not a **primitive recursive** function. In other words, you can implement an algorithm to express the function using **while-loops** (= computable), but still you cannot write an equivalent algorithm using only **do-loops** (= not primitive recursive). I suggest you to try this statement.

The function has this form:

As you can see, it's form is **fairly simple**. But, even if it seems simple, its values explode quickly. *A(4, 2)*, for example, has more than **19.000 digits**.

Representation of the Ackermann Function on the complex plane

What I want to talk about is the possible implementation of such a function by means of a computer algorithm. I will use **Python** for the next examples, but the description is language-independent.

Continue reading →