פונקציית אקרמן היא דוגמה פשוטה לפונקציה רקורסיבית שאיננה רקורסיבית פרימיטיבית . פונקציה זו גדלה מהר יותר מכל פונקציה רקורסיבית פרימיטיבית. לשם המחשה, (4,2)A, בבסיס 10, הוא מספר בן 19,729 ספרות.
הפונקציה קרויה על-שם מי שהגדיר אותה, בשנת 1928 , המתמטיקאי הגרמני וילהלם אקרמן .
פונקציית אקרמן מחושבת על ידי ההגדרה הרקורסיבית הבאה:
A
(
m
,
n
)
=
{
n
+
1
if
m
=
0
A
(
m
−
1
,
1
)
if
m
>
0
and
n
=
0
A
(
m
−
1
,
A
(
m
,
n
−
1
)
)
if
m
>
0
and
n
>
0
{\displaystyle A(m,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A(m-1,A(m,n-1))&{\mbox{if }}m>0{\mbox{ and }}n>0\end{cases}}}
עבור
m
{\displaystyle m}
n
{\displaystyle n}
טבעיים .
ניתן לבטא את פונקציית אקרמן במונחי החץ של קנות' והחץ של קונוויי .
הזהויות הן (
m
>
2
{\displaystyle m>2}
n
{\displaystyle n}
החץ של קנות':
A
(
m
,
n
)
=
2
↑
m
−
2
(
n
+
3
)
−
3
{\displaystyle A(m,n)=2\uparrow ^{m-2}(n+3)-3}
החץ של קונוויי:
A
(
m
,
n
)
=
(
2
→
(
n
+
3
)
→
(
m
−
2
)
)
−
3
{\displaystyle A(m,n)=(2\rightarrow (n+3)\rightarrow (m-2))-3}
