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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

הגדרה[עריכת קוד מקור | עריכה]

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

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

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

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

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

דוגמה[עריכת קוד מקור | עריכה]

נחשב את הערך :

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ אקרמן עבר את מלחמת העולם השנייה באוניברסיטת גטינגן שהולאמה תחת המשטר הנאצי מאז 1933, וחוקריה היהודים סולקו ממנה. לאחר המלחמה הוא נחקר בידי האמריקאים במשפטי נירנברג בחשד לחברות במפלגה הנאצית. ראו רשימת הנחקרים באתר הארכיב הממשלתי של ארצות הברית. בוויקיפדיה באנגלית סומן בקטגוריה כבן הכנסייה הלותרנית, אך לא הובאה הוכחה לקביעה זו. לאחר המלחמה נותר בתפקידיו באוניברסיטת גטינגן.
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.