Ackermannfunktionen är ett exempel på en beräkningsbar funktion som inte är primitivt rekursiv.
Ackermannfunktionen definieras för icke-negativa heltal
m
{\displaystyle m}
n
{\displaystyle n}
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
{\displaystyle m>3}
A
(
m
,
n
)
{\displaystyle A(m,n)}
A
(
4
,
2
)
{\displaystyle A(4,2)}
För specifika värden på
n
{\displaystyle n}
m
<
4
{\displaystyle m<4}
A
(
m
,
n
)
{\displaystyle A(m,n)}
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
{\displaystyle m}
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
)
{\displaystyle A(4,2)}
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
)
≈
19728
,
3
{\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.
Värden på
A
(
m
,
n
)
{\displaystyle A(m,n)}
n
{\displaystyle n}
0
1
2
3
4
n
{\displaystyle n}
m
{\displaystyle m}
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}
