פונקציית אקרמן

וילהלם אקרמן

פונקציית אקרמן היא דוגמה פשוטה לפונקציה רקורסיבית שאיננה רקורסיבית פרימיטיבית. פונקציה זו גדלה מהר יותר מכל פונקציה רקורסיבית פרימיטיבית. לשם המחשה, $A(4,2)$, בבסיס 10, הוא מספר בן 19,729 ספרות.

הפונקציה קרויה על-שם מי שהגדיר אותה, בשנת 1928, המתמטיקאי הגרמני וילהלם אקרמן.

הגדרה

פונקציית אקרמן מחושבת על ידי ההגדרה הרקורסיבית הבאה:

$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$ ו-$n$ טבעיים.

ניתן לבטא את פונקציית אקרמן במונחי החץ של קנות' והחץ של קונוויי.

הזהויות הן ($m>2$ ו-$n$ טבעיים):

• החץ של קנות':  $A(m,n)=2\uparrow ^{m-2}(n+3)-3$
• החץ של קונוויי:  $A(m,n)=(2\rightarrow (n+3)\rightarrow (m-2))-3$

דוגמה

נחשב את הערך $A(2,2)$:

${\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}}$

לעומתו, ניתן לראות כי:

${\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}}$

כלומר ההפרש הוא עצום.

ראו גם

• מספרים גדולים

קישורים חיצוניים

• פונקציית אקרמן, באתר אנציקלופדיה למתמטיקה (באנגלית)
• פונקציית אקרמן, באתר MathWorld (באנגלית)
• The Most Difficult Program to Compute?‎, סרטון בערוץ Computerphile באתר יוטיוב (אורך: 14:55) (באנגלית)

הערות שוליים

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.