The function A defined inductively on pairs of nonnegative integers in the following manner:
A(0,n) = n + 1
A(m+1,0) = A(m,1)
A(m+1,n+1) = A(m,A(m+1,n)) where m,n ≥ 0. Thus
A(1,n) = n + 2
A(2,n) = 2n + 3
A(3,n) = 2n+3 - 3 The highly recursive nature of the function makes it a popular choice for testing the ability of compilers or computers to handle recursion. It provides an example of a function that is general recursive but not primitive recursive because of the exceedingly rapid growth in its value as m increases.
The Ackermann function may also be regarded as a function Ack of a single variable:
Ack(n) = A(n,n)
where A is defined as above.