Ackermann Function

The Ackermann function is a function in computability theory, named after Wilhelm Ackermann, and it is one of the simplest and earliest known examples of a total computable function that is not primitive recursive. Its significance lies in showing that not every total computable function is primitive recursive, since the Ackermann function grows far faster than any primitive recursive function can. The version now most commonly used is the two argument Ackermann-Peter function, refined by Rozsa Peter and Raphael Robinson from Ackermanns original three argument function published in 1928; it grows so quickly that, for example, A(4,2) is an integer with 19,729 decimal digits. Ackermann discovered his function while a student of David Hilbert, working alongside Gabriel Sudan, who independently found a similarly fast growing total computable function around the same time.