Ackermann function

The Ackermann function (also known as Ackermann-Peter function), an important example in the theory of computation, is a recursive function which takes two natural numbers as arguments and returns a natural number as its value.

Table of contents

1 Definition 2 Recursive, but not primitive recursive 3 Explicit description 4 History 5 Inverse

Definition

The Ackermann function is defined by recursion as follows:

A(0, n) = n + 1    for n ≥ 0

A(m, 0) = A(m - 1, 1)    for m ≥ 1

A(m, n) = A(m - 1, A(m, n - 1))    for m, n ≥ 1

The Ackermann function grows extremely fast; A(4,2) is already about 2.0035299*10¹⁹⁷²⁸. This extreme growth can be exploited to show that the computable function f(n) = A(n, n) grows faster than any primitive recursive function and is therefore not primitive recursive.

Explicit description

Intuitively, the Ackermann function defines generalizations of multiplication by two (iterated additions) and exponentiation with base 2 (iterated multiplications) to iterated exponentiation, iteration of this operation and so on. It can be most concisely expressed nonrecursively using Conway's arrow:

In 1928, Wilhelm Ackermann considered a function A(m, n, p) of three variables, the p-fold iterated exponentiation of m with n, and proved that it is a recursive function which is not primitive recursive. This definition was later simplified by Rosza Peter and Raphael Robinson to the two-variable definition given above.

Inverse

Since the function f(n) = A(n,n) considered above grows very rapidly, its inverse grows very slowly; this inverse occurs in the run-time analysis of certain algorithms.