Ackerman(4, 4)

 Retrospectively, it seems that younger, I was trying to be a bit different from the average people around me. At university, where people often had long hair, I was rather clean cut. Here is a passport photo from some later time, while working with straight looking guys. Nowadays, no need distinguishing myself anymore: aging alone takes good care of this! ☺

Here a Python version of the Ackerman function:

        def Ackerman(i, j):

        if i == 0:

         return j + 1

       if j == 0:

         return Ackerman(i-1, 1)

            return Ackerman(i-1, Ackerman(i, j-1))

I first read about it when I was a teenager, just starting university. Algol (that is: Algol-60) was not taught, but yet, my friends and I were pretty curious, so when we found Christian Boitet's book about this language, we closely studied it, and this is where we read a definition for the Ackerman function.

Of course, we tried it for small values of and , and were amazed to see the intense recursion, and the numbers it could produce. After all, the most aggressive operation towards bloating the resulting value is adding 1 to . However, we found out that none of us could climb the arguments to 4 and 4, and it soon became a challenge between us. We tried hard, with every computing language we knew, but were invariably stopped by the limit of 10 CPU seconds per job for students.

Between my first and second year, I got a permanent job in the systems analyst group of the computer center, and with it, extended capabilities for using the machine. Still a student nevertheless, and with the same gang of friends, I wrote a tightly coded assembler program for computing , and got permission to run it as a low priority job, so to not disrupt operations nor impact users. Using checkpoints and restarts to go through scheduled system deadstarts, I let it run for many weeks, but at no time I even saw the shadow of a success.

This whole effort became a running gag in the gang. For some of us, even once graduated and out of the university, randomly walking on one another on the street, we would say So, what's ? instead of Hello!. Something like ten years later, sharing a dinner with Claude Goutier, a friend from those times, and like always, we filled napkins and napkins with drawings and formulas while discussing of various things, the Ackerman problem among others. This very evening, for an unrelated reason, I had to spend the whole night awake and waiting. To kill time (and slightly angry at myself for never having much tried anything else than brute force before), I worked out as being equivalent to:

Of course, I always knew that was an fairly odd value, but now, I had a proof that it was exactly an odd number! ☺ Glad to have an explicit result, I phoned Claude on the next morning, who coincidentally, after our meal, worked out the same result as well, on his side.

With this explicit formulation in hand, I could illustrate why we all failed at computing the monster when we were younger. Indeed, is a tremendously big number. If each elementary particle of the universe was a blob of ink with which we could write one digit of the resulting number, the whole universe could not provide enough ink to write the result. No wonder then, that the big mainframe of the computer center would never have had enough memory.

What about time as a resource? How much time could take the computation of this number? Let's suppose first that I have a very, very fast computer, with a very short clock cycle. How short could a computer cycle can be? I decided for a lower bound: the time it would take for the fastest thing I know to travel the smallest physical distance I could imagine. So, the time taken by a light ray through a proton diameter (most people know that a proton is much thinner than an electron, even if quite heavier). So, with such a fast computer, able to perform one addition per cycle, if it started to compute exactly when the big bang created our universe, this universe would still be, and by far, much too young for the result to come out.

Isn't it fascinating that such big a number, while being undoubtedly both well defined and computable theoretically, yet intractable in practice, could be represented by so little code?