# 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

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.

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