Ackermannfunktionen

Ackermannfunktionen är ett exempel på en beräkningsbar funktion som inte är primitivt rekursiv.

Ackermannfunktionen definieras för icke-negativa heltal $m$ och $n$ enligt: $A(m,n)=\{\begin{array}{cc}n+1& m=0\\ A(m-1,1)& m>0,n=0\\ A(m-1,A(m,n-1))& m>0,n>0.\end{array}$

Från definitionen syns tydligt att för $m>3$ växer $A(m,n)$ väldigt snabbt, redan för låga värden på n. Exempelvis är $A(4,2)$ skrivet i decimal form ett heltal med över 19 000 siffror.

För specifika värden på $n$, då $m<4$ kan $A(m,n)$ beskrivas med relativt enkla medel:

$A(m,n)=\{\begin{array}{cc}n+1& m=0\\ n+2& m=1\\ 2n+3& m=2\\ 2^{n+3}-3& m=3\end{array}$

För större värden på $m$ växer funktionen alltför snabbt för att beskrivas med några av de elementära räknesätten. I stället kan Knuths pilnotation användas.

Generellt gäller att

$A(m,n)=2{\uparrow }^{m-2}(n+3)-3.$

Med hjälp av denna beskrivning kan rekursionen av $A(4,2)$ göras något enklare.

$A(4,2)=2{\uparrow }^{4-2}(2+3)-3=2{\uparrow }^2(5)-3=2\uparrow 2\uparrow 2\uparrow 2\uparrow 2-3=2^{2^{2^{2^2}}}-3=2^{65536}-3$

Och då

$\log (2^{65536})=65536\cdot \log (2)\approx 19728,3$

förstås att detta tal utskrivet i decimal form har 19 729 siffror.

Ackermannstal

Värden på $A(m,n)$

		$n$
		0	1	2	3	4	$n$
$m$	0	1	2	3	4	5	$n+1$
	1	2	3	4	5	6	$n+2=2+(n+3)-3$
	2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
	3	5	13	29	61	125	$2^{(n+3)}-3$
	4	13 =$2^{2^2}-3$	65533 =$2^{2^{2^2}}-3$	265536 − 3 =$2^{2^{2^{2^2}}}-3$	$2^{2^{65536}}-3$ =$2^{2^{2^{2^{2^2}}}}-3$	$2^{2^{2^{65536}}}-3$ =$2^{2^{2^{2^{2^{2^2}}}}}-3$	$\begin{array}{c}\underbrace{{2^2}^{{\cdot }^{{\cdot }^{{\cdot }^2}}}}-3\\ n+3\end{array}$
	5	65533 =$2\uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow (n+3)-3$
	6	$2\uparrow \uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow \uparrow (n+3)-3$

Se även

• Wilhelm Ackermann