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.

Title	Ackermann function
Canonical name	AckermannFunction
Date of creation	2013-03-22 12:33:13
Last modified on	2013-03-22 12:33:13
Owner	akrowne (2)
Last modified by	akrowne (2)
Numerical id	9
Author	akrowne (2)
Entry type	Definition
Classification	msc 03D75