Malevolent Ackermann

The Ackermann function is a lot of fun because it grows extremely quickly. It’s total, meaning for each element in its domain (two natural numbers), it gives back a value. It’s computable, meaning that if you had infinite time you could find the result by programming a computer to run an algorithm that calculates the result of the function.

It’s also not primitive recursive, which for our purposes here really just means that it grows super duper unusually fast. Most more-familiar computable functions are primitive recursive, since they’re constructed from substitution and primitive recursion. Fittingly then, the Ackermann function is infamous for being a total computable function that’s not primitive recursive.

A common modern representation of this function comes in three cases that look deceivingly simple. All they really do is add or subtract one, and recurse in various ways. This has a very natural (pun somewhat intended) implementation in Idris:

A : Nat -> Nat -> Nat
A Z n = S n
A (S m) Z = A m (S Z)
A (S m) (S n) = A m (A (S m) n)

This function produces very large values even for somewhat small values of m and n. Don’t try running A 5 5!

Another kind of computational process that tends to grow very quickly is a fork bomb. This is a process that keeps reproducing copies of itself, wasting system resources. Here’s a classic example of a fork bomb in C:

int main() {
  while (1) {
    fork();
  }
}

At each step of the loop, we generate another process that itself will run its own loop and fork off its own child processes. If your OS doesn’t manage to save you from yourself, you’re very quickly going to run out of resources and encounter a nice system crash.

Putting together the ideas of the fast-growing Ackermann function, and a fork bomb, we can come up with a very fast-growing fork bomb. Of course, for practical purposes this isn’t really necessary since forking a new process at each step of the while loop, from each running process, will quickly exhaust finite computer resources. But it’s fun to think about just how fast this hypothetically drains resources, even if on an actual computer it’s slower (because it has to do more work that isn’t just forking another process).