Ackermann function

Example

The Ackermann function, in the two-argument form of Rózsa Péter, is the function $A \colon \N \times \N \to \N$ given by $$A(0, n) = n + 1, \qquad A(m + 1, 0) = A(m, 1), \qquad A(m + 1, n + 1) = A(m, A(m + 1, n)).$$ It is a total computable function. Each right-hand side calls $A$ at a pair that is smaller in the lexicographic order on $\N \times \N$. This order is a well-order, so the recursion stops on every input and gives an algorithm for $A$.