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

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

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

הגדרהעריכה

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

 

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

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

הזהויות הן (  ו-  טבעיים):

  • החץ של קנות':   
  • החץ של קונוויי:   

דוגמהעריכה

נחשב את הערך  :

 

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

 

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

ראו גםעריכה

קישורים חיצונייםעריכה

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