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

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

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

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

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

A(m,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A(m-1,A(m,n-1))&{\mbox{if }}m>0{\mbox{ and }}n>0\end{cases}}

עבור $m$ ו- $n$ טבעיים.

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

הזהויות הן ( $m>2$ ו- $n$ טבעיים):

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

${\begin{aligned}A(2,2)&=A(1,A(2,1))\\&=A(1,A(1,A(1,0)))\\&=A(1,A(1,A(0,1)))\\&=A(1,A(1,2))\\&=A(1,A(0,A(1,1)))\\&=A(1,A(0,A(0,A(1,0))))\\&=A(1,A(0,A(0,A(0,1))))\\&=A(1,A(0,A(0,2)))\\&=A(1,A(0,3))\\&=A(1,4)\\&=A(0,A(1,3))\\&=A(0,A(0,A(1,2)))\\&=A(0,A(0,A(0,A(1,1))))\\&=A(0,A(0,A(0,A(0,A(1,0)))))\\&=A(0,A(0,A(0,A(0,A(0,1)))))\\&=A(0,A(0,A(0,A(0,2))))\\&=A(0,A(0,A(0,3)))\\&=A(0,A(0,4))=A(0,5)\\&=6\end{aligned}}$

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

${\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^{\overset {65536}{}}}-3.\\\end{aligned}}$