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\approx 2.003529930406846\times 10^{19728}}$

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.

• Wilhelm Ackermann