Ackermann's function proved some computable things outrun simple step-by-step recursion
In 1928 Wilhelm Ackermann, a former student of David Hilbert who was then working as his personal secretary, published a function that any computer could in principle evaluate but that grows too fast to be built from the basic loop-like recipes called primitive recursion. It became one of the earliest and simplest examples of that gap.
Hilbert had guessed in his essay On the Infinite that such a function existed. Ackermann supplied the proof, in a paper on Hilbert's construction of the real numbers. Another Hilbert student, Gabriel Sudan, had found a similar, less famous function shortly before, and both are credited with the discovery. At the time the two were probing the foundations of computation.
Ackermann's original took three inputs, and the third acted as a dial for how powerful the operation is. Set it to 0 and the function adds two numbers, to 1 and it multiplies, to 2 and it raises one to the power of the other. Turning the dial higher produces operations beyond exponentiation, towers of repeated powers, which is where the explosive growth comes from.
Many variants followed, so the Ackermann function now names a whole family. The version most authors mean is a two-input form developed by Rózsa Péter and Raphael Robinson, defined by a short recursive rule in which the function calls itself inside its own argument. In 1963 R. Creighton Buck offered a tidier variant without awkward offsets: level 0 adds one, level 1 adds two, level 2 doubles, level 3 gives powers of 2, and level 4 stacks towers of 2s.
Mathematically, the function works by diagonalising, running along an ever-faster sequence of primitive recursive functions and outpacing every one of them. That is why it sits just beyond their reach while remaining completely computable.
Source: Ackermann function
