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 Gnx 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 9 November 2020.
HTML page formatted Wed Oct 30 12:15:30 2024.
Cite this as:
Paul E. Black, "Ackermann's function", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 9 November 2020. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/ackermann.html