Ackermannfunktionen

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

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

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

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

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

För större värden på ${\displaystyle 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

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

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

${\displaystyle 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å

${\displaystyle \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å ${\displaystyle A(m,n)}$

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

Se även

• Wilhelm Ackermann