וילהלם אקרמן פונקציית אקרמן היא דוגמה פשוטה לפונקציה רקורסיבית שאיננה רקורסיבית פרימיטיבית . פונקציה זו גדלה מהר יותר מכל פונקציה רקורסיבית פרימיטיבית. לשם המחשה,
A
(
4
,
2
)
{\displaystyle A(4,2)}
הפונקציה קרויה על-שם מי שהגדיר אותה, בשנת 1928 , המתמטיקאי הגרמני וילהלם אקרמן .[1]
הגדרה פונקציית אקרמן מחושבת על ידי ההגדרה הרקורסיבית הבאה:
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}
דוגמה נחשב את הערך
A
(
2
,
2
)
{\displaystyle A(2,2)}
A
(
2
,
2
)
=
A
(
1
,
A
(
2
,
1
)
)
=
A
(
1
,
A
(
1
,
A
(
1
,
0
)
)
)
=
A
(
1
,
A
(
1
,
A
(
0
,
1
)
)
)
=
A
(
1
,
A
(
1
,
2
)
)
=
A
(
1
,
A
(
0
,
A
(
1
,
1
)
)
)
=
A
(
1
,
A
(
0
,
A
(
0
,
A
(
1
,
0
)
)
)
)
=
A
(
1
,
A
(
0
,
A
(
0
,
A
(
0
,
1
)
)
)
)
=
A
(
1
,
A
(
0
,
A
(
0
,
2
)
)
)
=
A
(
1
,
A
(
0
,
3
)
)
=
A
(
1
,
4
)
=
A
(
0
,
A
(
1
,
3
)
)
=
A
(
0
,
A
(
0
,
A
(
1
,
2
)
)
)
=
A
(
0
,
A
(
0
,
A
(
0
,
A
(
1
,
1
)
)
)
)
=
A
(
0
,
A
(
0
,
A
(
0
,
A
(
0
,
A
(
1
,
0
)
)
)
)
)
=
A
(
0
,
A
(
0
,
A
(
0
,
A
(
0
,
A
(
0
,
1
)
)
)
)
)
=
A
(
0
,
A
(
0
,
A
(
0
,
A
(
0
,
2
)
)
)
)
=
A
(
0
,
A
(
0
,
A
(
0
,
3
)
)
)
=
A
(
0
,
A
(
0
,
4
)
)
=
A
(
0
,
5
)
=
6
{\displaystyle {\begin{aligned}A(2,2)&=A(1,A(2,1))\\&=A(1,A(1,A(1,0)))\\&=A(1,A(1,A(0,1)))\\&=A(1,A(1,2))\\&=A(1,A(0,A(1,1)))\\&=A(1,A(0,A(0,A(1,0))))\\&=A(1,A(0,A(0,A(0,1))))\\&=A(1,A(0,A(0,2)))\\&=A(1,A(0,3))\\&=A(1,4)\\&=A(0,A(1,3))\\&=A(0,A(0,A(1,2)))\\&=A(0,A(0,A(0,A(1,1))))\\&=A(0,A(0,A(0,A(0,A(1,0)))))\\&=A(0,A(0,A(0,A(0,A(0,1)))))\\&=A(0,A(0,A(0,A(0,2))))\\&=A(0,A(0,A(0,3)))\\&=A(0,A(0,4))=A(0,5)\\&=6\end{aligned}}}
לעומתו, ניתן לראות כי:
A
(
4
,
3
)
=
A
(
3
,
A
(
4
,
2
)
)
=
A
(
3
,
A
(
3
,
A
(
4
,
1
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
4
,
0
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
3
,
1
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
3
,
0
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
2
,
1
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
1
,
A
(
2
,
0
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
1
,
A
(
1
,
1
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
1
,
A
(
0
,
A
(
1
,
0
)
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
1
,
A
(
0
,
A
(
0
,
1
)
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
1
,
A
(
0
,
2
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
1
,
3
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
0
,
A
(
1
,
2
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
0
,
A
(
0
,
A
(
1
,
1
)
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
0
,
A
(
0
,
A
(
0
,
A
(
1
,
0
)
)
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
0
,
A
(
0
,
A
(
0
,
A
(
0
,
1
)
)
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
0
,
A
(
0
,
A
(
0
,
2
)
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
0
,
A
(
0
,
3
)
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
A
(
0
,
4
)
)
)
)
)
=
A
(
3
,
A
(
3
,
A
(
3
,
A
(
2
,
5
)
)
)
)
=
…
=
A
(
3
,
A
(
3
,
A
(
3
,
13
)
)
)
=
…
=
A
(
3
,
A
(
3
,
65533
)
)
=
…
=
A
(
3
,
2
65536
−
3
)
=
…
=
2
2
65536
−
3.
{\displaystyle {\begin{aligned}A(4,3)&=A(3,A(4,2))\\&=A(3,A(3,A(4,1)))\\&=A(3,A(3,A(3,A(4,0))))\\&=A(3,A(3,A(3,A(3,1))))\\&=A(3,A(3,A(3,A(2,A(3,0)))))\\&=A(3,A(3,A(3,A(2,A(2,1)))))\\&=A(3,A(3,A(3,A(2,A(1,A(2,0))))))\\&=A(3,A(3,A(3,A(2,A(1,A(1,1))))))\\&=A(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))\\&=A(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))\\&=A(3,A(3,A(3,A(2,A(1,A(0,2))))))\\&=A(3,A(3,A(3,A(2,A(1,3)))))\\&=A(3,A(3,A(3,A(2,A(0,A(1,2))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(0,2)))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,3))))))\\&=A(3,A(3,A(3,A(2,A(0,4)))))\\&=A(3,A(3,A(3,A(2,5))))\\&=\ldots \\&=A(3,A(3,A(3,13)))\\&=\ldots \\&=A(3,A(3,65533))\\&=\ldots \\&=A(3,2^{65536}-3)\\&=\ldots \\&=2^{2^{\overset {65536}{}}}-3.\\\end{aligned}}}
כלומר ההפרש הוא עצום.
ראו גם קישורים חיצוניים הערות שוליים
↑ אקרמן עבר את מלחמת העולם השניה באוניברסיטת גטינגן שהולאמה תחת המשטר הנאצי מאז 1933, וחוקריה היהודים סולקו ממנה. לאחר המלחמה הוא נחקר בידי האמריקאים במשפטי נירנברג בחשד לחברות במפלגה הנאצית. ראו רשימת הנחקרים באתר הארכיב הממשלתי של ארה"ב. בויקיפדיה באנגלית סומן בקטגוריה כבן הכנסיה הלותרנית, אך לא הובאה הוכחה לקביעה זו. לאחר המלחמה נותר בתפקידיו באוניברסיטת גטינגן.
פונקציית אקרמן 33957816 Q341835
The Most Difficult Program to Compute?, סרטון בערוץ Computerphile באתר יוטיוב (אורך: 14:55) (באנגלית)
