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

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

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

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

עבור  ו- טבעיים.

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

הזהויות הן ( ו- טבעיים):
 החץ של קנות':
 החץ של קונוויי:

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

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

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

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

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

הערות שוליים

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