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

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

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.

History

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 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
Canadian Music Hall of Fame

... Gould 1986 Gordon Lightfoot 1987 The Guess Who[?] 1989 The Band 1990 Maureen Forrester[?] 1991 Leonard Cohen 1992 Ian and Sylvia[?] 1993 Anne Murray 1994 ...

 
 
 
This page was created in 36.5 ms