Ackermann Function - Definition and Properties

Definition and Properties

Ackermann's original three-argument function is defined recursively as follows for nonnegative integers m, n, and p:

Of the various two-argument versions, the one developed by Péter and Robinson (called "the" Ackermann function by some authors) is defined for nonnegative integers m and n as follows:

It may not be immediately obvious that the evaluation of always terminates. However, the recursion is bounded because in each recursive application either m decreases, or m remains the same and n decreases. Each time that n reaches zero, m decreases, so m eventually reaches zero as well. (Expressed more technically, in each case the pair (m, n) decreases in the lexicographic order on pairs, which is a well-ordering, just like the ordering of single non-negative integers; this means one cannot go down in the ordering infinitely many times in succession.) However, when m decreases there is no upper bound on how much n can increase — and it will often increase greatly.

The Péter-Ackermann function can also be expressed in terms of various other versions of the Ackermann function:

• the indexed version of Knuth's up-arrow notation (extended to integer indices ≥ -2):

A(m, n) =

The part of the definition A(m, 0) = A(m-1, 1) corresponds to

• hyper operators:

A(m, n) = hyper(2, m, n + 3) − 3.

• Conway chained arrow notation:

A(m, n) = (2 → (n+3) → (m − 2)) − 3 for m > 2

hence

2 → n → m = A(m+2,n-3) + 3 for n>2.

(n=1 and n=2 would correspond with A(m,−2) = −1 and A(m,−1) = 1, which could logically be added.)

For small values of m like 1, 2, or 3, the Ackermann function grows relatively slowly with respect to n (at most exponentially). For m ≥ 4, however, it grows much more quickly; even A(4, 2) is about 2×1019,728, and the decimal expansion of A(4, 3) is very large by any typical measure.

If we define the function f (n) = A(n, n), which increases both m and n at the same time, we have a function of one variable that dwarfs every primitive recursive function, including very fast-growing functions such as the exponential function, the factorial function, multi- and superfactorial functions, and even functions defined using Knuth's up-arrow notation (except when the indexed up-arrow is used).

This extreme growth can be exploited to show that f, which is obviously computable on a machine with infinite memory such as a Turing machine and so is a computable function, grows faster than any primitive recursive function and is therefore not primitive recursive. In a category with exponentials, using the isomorphism (in computer science, this is called currying), the Ackermann function may be defined via primitive recursion over higher-order functionals as follows:

where Succ is the usual successor function and Iter is defined by primitive recursion as well:

One interesting aspect of the Ackermann function is that the only arithmetic operations it ever uses are addition and subtraction of 1. Its properties come solely from the power of unlimited recursion. This also implies that its running time is at least proportional to its output, and so is also extremely huge. In actuality, for most cases the running time is far larger than the output; see below.