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

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

A(m,n) מוגדרת רקורסיבית כך: אם m=0 אז A(m,n)=n+1. אם m>0 ו-n=0 אז A(m,n)=A(m-1,1). אם m>0 ו-n>0 אז A(m,n)=A(m-1,A(m,n-1)). כאן m ו-n הם מספרים טבעיים. הנוסחה הזו מבססת קריאות חוזרות רבות, ולכן הצמיחה שלה מאוד חדה.

חישוב קצר מראה ש-A(2,2)=7. לעומת זאת, חישובים נרחבים מראים ש-A(4,3) מגיע לערכים עצומים, וביטוי אחד שלה מסתיים כמבנה דמוי חזקות מרובות שעשוי להיכתב כ-2 בחזקת 2 בחזקת 65536 פחות 3. ההבדל בין A(2,2) ל-A(4,3) ממחיש עד כמה פונקציית אקרמן יכולה לגדול מהר.

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

החוק עובד בשלושה מקרים פשוטים: אם m שווה 0 מוסיפים 1 ל-n. אם m גדול מ-0 ו-n שווה 0 מחזירים ערך עם m-1 ו-1. אם שניהם גדולים, קוראים קודם ל-A(m,n-1) ואז ל-A(m-1,...) שוב.

A(2,2) נותן 7. A(4,2) הוא מספר ענק עם 19,729 ספרות. A(4,3) הוא מספר עצום עוד יותר, הרבה מעבר למה שקל לדמיין.