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.

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 Black.

Entry modified 4 October 2010.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "Ackermann's function", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 4 October 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/ackermann.html