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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

פונקציית אקרמן היא דוגמה פשוטה לפונקציה רקורסיבית שאיננה רקורסיבית פרימיטיבית. פונקציה זו גדלה מהר יותר מכל פונקציה רקורסיבית פרימיטיבית. לשם המחשה, (4,2)A, בבסיס 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

ראו גם[עריכת קוד מקור | עריכה]

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