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: Many people have defined other similar functions which are not simply a restating of this one.

In 1928, Wilhelm Ackermann observed that A(x,y,z), the z-fold iterated exponentiation of x with y, is a recursive function that 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.

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.

Wilhelm Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Mathematische Annalen 99(1):118-133, December 1928.
doi:10.1007/BF01459088

The formal definition given here is G_nx in the first page of
Raphael M. Robinson, Recursion and Double Recursion, Bulletin of the American Mathematical Society 54:987-993, October 1948.
doi:10.1090/S0002-9904-1948-09121-2

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 31 July 2008.
HTML page formatted Wed Feb 4 11:02:21 2009.

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. 31 July 2008. (accessed TODAY) Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/ackermann.html