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

וילהלם אקרמן

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

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

הגדרה

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

$A(m,n)=\{\begin{array}{ll}n+1& :m=0\\ A(m-1,1)& :m>0,n=0\\ A(m-1,A(m,n-1))& :m>0,n>0\end{array}$

עבור $m,n$ טבעיים.

ניתן לבטא את פונקציית אקרמן במונחי החץ של קנות' והחץ של קונוויי. הזהויות הן ($m>2,n$ טבעיים):

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

דוגמה

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

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

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

$\begin{array}{rl}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))))\\ & =\dots \\ & =A(3,A(3,A(3,13)))\\ & =\dots \\ & =A(3,A(3,65533))\\ & =\dots \\ & =A(3,2^{65536}-3)\\ & =\dots \\ & =2^{2^{65536}}-3\end{array}$

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

ראו גם

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

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

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

הערות שוליים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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