Encyclopedia > Ackermann function

  Article Content

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


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

Recursive, but not primitive recursive

The Ackermann function grows extremely fast; A(4,2) already has 19,729 digits. 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 using Knuth's up-arrow notation:

A(1, n) = 2 + (n + 3) - 3
A(2, n) = 2 * (n + 3) - 3
A(3, n) = 2 ^ (n + 3) - 3
A(4, n) = 2 ^ (2 ^ (2 ^ (.... ^2))) - 3     (n + 3 twos)
            = 2^^(n + 3) - 3
A(5, n) = 2^^^(n + 3) - 3 etc.


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.


Since the function f(n) = A(n,n) considered above grows really fast, its inverse grows really slowly. Interestingly, this inverse occurs in the run-time analysis of some algorithms.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Sanskrit language

... has a voiceless, voiceless aspirate, voiced, voiced aspirate, and nasal stop at each of the following places of articulation: Velar (soft palate[?]) (k, ...

This page was created in 32.4 ms