# 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_{n}x 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 Mon Dec 21 09:49:05 2020.

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