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
)
=
{
n
+
1
m
=
0
A
(
m
−
1
,
1
)
m
>
0
,
n
=
0
A
(
m
−
1
,
A
(
m
,
n
−
1
)
)
m
>
0
,
n
>
0.
{\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 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å, då m<4 kan A(m,n) beskrivas med relativt enkla medel.
A
(
m
,
n
)
=
{
n
+
1
m
=
0
n
+
2
m
=
1
2
n
+
3
m
=
2
2
n
+
3
−
3
m
=
3
{\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å m växer dock funktionen alltför snabbt för att beskrivas med några av de elementära räknesätten. Istället kan exempelvis Knuths pilnotation användas.
Generellt gäller att
A
(
m
,
n
)
=
2
↑
m
−
2
(
n
+
3
)
−
3.
{\displaystyle 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
↑
4
−
2
(
2
+
3
)
−
3
=
2
↑
2
(
5
)
−
3
=
2
↑
2
↑
2
↑
2
↑
2
−
3
=
2
2
2
2
2
−
3
=
2
65536
−
3
{\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å
log
(
2
65536
)
=
65536
(
log
(
2
)
)
{\displaystyle \log(2^{65536})=65536(\log(2))}
syns att detta tal utskrivet i decimal form skulle ha 19729 siffror.
Ackermannstal
Värden på A (m , n )
m \n
0
1
2
3
4
n
0
1
2
3
4
5
n
+
1
{\displaystyle n+1}
1
2
3
4
5
6
n
+
2
=
2
+
(
n
+
3
)
−
3
{\displaystyle n+2=2+(n+3)-3}
2
3
5
7
9
11
2
n
+
3
=
2
⋅
(
n
+
3
)
−
3
{\displaystyle 2n+3=2\cdot (n+3)-3}
3
5
13
29
61
125
2
(
n
+
3
)
−
3
{\displaystyle 2^{(n+3)}-3}
4
13
2
2
2
−
3
{\displaystyle {2^{2^{2}}}-3}
65533
2
2
2
2
−
3
{\displaystyle {2^{2^{2^{2}}}}-3}
265536 − 3
2
2
2
2
2
−
3
{\displaystyle {2^{2^{2^{2^{2}}}}}-3}
2
2
65536
−
3
{\displaystyle {2^{2^{65536}}}-3}
2
2
2
2
2
2
−
3
{\displaystyle {2^{2^{2^{2^{2^{2}}}}}}-3}
2
2
2
65536
−
3
{\displaystyle {2^{2^{2^{65536}}}}-3}
2
2
2
2
2
2
2
−
3
{\displaystyle {2^{2^{2^{2^{2^{2^{2}}}}}}}-3}
2
2
⋅
⋅
⋅
2
⏟
−
3
n
+
3
{\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n+3\end{matrix}}}
5
65533
2
↑↑↑
3
−
3
{\displaystyle 2\uparrow \uparrow \uparrow 3-3}
2
↑↑↑
4
−
3
{\displaystyle 2\uparrow \uparrow \uparrow 4-3}
2
↑↑↑
5
−
3
{\displaystyle 2\uparrow \uparrow \uparrow 5-3}
2
↑↑↑
6
−
3
{\displaystyle 2\uparrow \uparrow \uparrow 6-3}
2
↑↑↑
7
−
3
{\displaystyle 2\uparrow \uparrow \uparrow 7-3}
2
↑↑↑
(
n
+
3
)
−
3
{\displaystyle 2\uparrow \uparrow \uparrow (n+3)-3}
6
2
↑↑↑↑
3
−
3
{\displaystyle 2\uparrow \uparrow \uparrow \uparrow 3-3}
2
↑↑↑↑
4
−
3
{\displaystyle 2\uparrow \uparrow \uparrow \uparrow 4-3}
2
↑↑↑↑
5
−
3
{\displaystyle 2\uparrow \uparrow \uparrow \uparrow 5-3}
2
↑↑↑↑
6
−
3
{\displaystyle 2\uparrow \uparrow \uparrow \uparrow 6-3}
2
↑↑↑↑
7
−
3
{\displaystyle 2\uparrow \uparrow \uparrow \uparrow 7-3}
2
↑↑↑↑
(
n
+
3
)
−
3
{\displaystyle 2\uparrow \uparrow \uparrow \uparrow (n+3)-3}
Se även 
