Ackermann function
Jump to navigation
Jump to search
The Ackermann function is probably the most well-known example of a function that is computable but which grows so extremely fast that it is not primitive recursive. Thus being able to calculate it is a test of the computational class of a language.
It is a function of two natural numbers, returning a natural number. Its definition is by recursion in two variables:
unsigned int A(unsigned int m,unsigned int n) {
if (m==0) { return n+1; }
else if (n==0) { return A(m-1,1); }
else { return A(m-1,A(m,n-1)); }
}