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

מתוך המכלול, האנציקלופדיה היהודית
גרסה מ־00:39, 24 בדצמבר 2017 מאת יהודה שמחה ולדמן (שיחה | תרומות) (הגהה, תיקון קישורים, הכנסת קודים מתמטיים ושיפוץ הקיימים)
קפיצה לניווט קפיצה לחיפוש

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

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

הגדרה

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

עבור טבעיים.

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

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

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

ראו גם

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.