# Ackermann function

Ackermann’s function $A(x,y)$ is defined by the recurrence relations

 $\displaystyle A(0,y)$ $\displaystyle=y+1$ $\displaystyle A(x+1,0)$ $\displaystyle=A(x,1)$ $\displaystyle A(x+1,y+1)$ $\displaystyle=A(x,A(x+1,y))$

Ackermann’s function grows extremely fast. In fact, we find that

 $\displaystyle A(0,y)$ $\displaystyle=$ $\displaystyle y+1$ $\displaystyle A(1,y)$ $\displaystyle=$ $\displaystyle 2+(y+3)-3$ $\displaystyle A(2,y)$ $\displaystyle=$ $\displaystyle 2\cdot(y+3)-3$ $\displaystyle A(3,y)$ $\displaystyle=$ $\displaystyle 2^{y+3}-3$ $\displaystyle A(4,y)$ $\displaystyle=$ $\displaystyle 2^{2^{{\ldotp\cdotp}^{2}}}-3\;\;\;\;(y+3\text{ exponentiations})$ $\displaystyle\cdots$

… and at this point conventional notation breaks down, and we need to employ something like Conway notation or Knuth notation for large numbers.

Ackermann’s function wasn’t actually written in this form by its namesake, Wilhelm Ackermann. Instead, Ackermann found that the $z$-fold exponentiation of $x$ with $y$ was an example of a recursive function which was not primitive recursive. Later this was simplified by Rosza Peter to a function of two variables, similar to the one given above.

Title Ackermann function  AckermannFunction 2013-03-22 12:33:13 2013-03-22 12:33:13 akrowne (2) akrowne (2) 9 akrowne (2) Definition msc 03D75