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

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

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

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

עבור ${\displaystyle m,n}$ טבעיים.

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

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

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

${\displaystyle {\begin{aligned}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{aligned))}$

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

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

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

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

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

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