Ackermann.
The Ackermann function is a prominent example of a recursive function. It is named after Wilhelm Ackermann (1886–1962). Many functions in mathematical practice are primitive recursive. In 1926, David Hilbert asked whether all functions whose arguments and values are natural numbers are primitive recursive. The Ackermann function grows extremely fast and serves as an example that there are computable functions that are not primitive recursive. In 1928, Ackermann demonstrated this using the Ackermann function. It grows faster than substitution and recursion allow. Only for small arguments can the function values still be calculated without recursion. This was also the idea behind Ackermann's proof. The original version is given by the following functional equation:
Instead, the variant by Hans Hermes is used, which is derived directly from the original. The function maps two integers to an integer a(n,m). It is defined mathematically by the following rules:
The Ackermann function is famous for exhausting computational resources very quickly. The definition according to Hermes can be translated almost 1:1 into Prolog:
It can then be executed with:
The result would be stored in the variable L. However, this leads to the following error:
With a smaller function call you get a result:
This clearly shows that even with small values the Ackermann function can run into memory limits.