Ackermann's function

(algorithm)

Definition: A function of two parameters whose value grows very fast.

Formal Definition:

A(0, j)=j+1 for j ≥ 0
A(i, 0)=A(i-1, 1) for i > 0
A(i, j)=A(i-1, A(i, j-1)) for i, j > 0

See also inverse Ackermann function.

Note: In 1928, Wilhelm Ackermann observed that A(x,y,z), the z-fold iterated exponentiation of x with y, is an example of a recursive function which is not primitive recursive. A(x,y,z) was simplified to a function of 2 variables by Rózsa Péter in 1935. Raphael M. Robinson simplified the initial condition in 1948.

Many people have given other versions of Ackermann's function, some of which are not simply a restating of this one.

Author: PEB

Implementation

History of the function and (Modula-2) code. (Lisp). (Pascal). (Miranda).

More information

Robert Munafo's Versions of Ackermann's Function and analysis. Cowles and Bailey Several Versions of Ackermann's function.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 28 April 2008.
HTML page formatted Mon May 12 09:12:57 2008.

Cite this as:
Paul E. Black, "Ackermann's function", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 28 April 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/ackermann.html