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 is an example of a recursive function that is not primitive recursive, but is instead $\\mu$ -recursive (that is, Turing-computable).

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.