## Quick Reference

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*) = 2*n* + 3

*A*(3,*n*) = 2* ^{n+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.

*Subjects:*
Computing.