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