The function A defined inductively on pairs of nonnegative integers in the following manner:
where
m,
n ≥ 0. Thus
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:
where A is defined as above.