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

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

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

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

עבור  טבעיים.

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

דוגמה
נחשב את הערך :

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

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

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

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



הערות שוליים

קטגוריה:רקורסיה
קטגוריה:פונקציות בעלות גידול על-מעריכי
אקרמן