دالة أكرمان

في نظرية الحوسبة ، تُعد دالة أكرمان ، نسبةً إلى ويلهلم أكرمان ، من أبسط الأمثلة ^{[ 1 ]} وأقدمها اكتشافًا لدالة قابلة للحوسبة الكلية وليست دالة تكرارية بدائية . جميع الدوال التكرارية البدائية كلية وقابلة للحوسبة، لكن دالة أكرمان تُبين أن ليس كل الدوال القابلة للحوسبة الكلية تكرارية بدائية. وهي تُبنى أساسًا عن طريق قطريّة سلسلة من الدوال التكرارية البدائية. $f_{1},f_{2},\dots$ مختارة من التسلسل الهرمي لغريغورتشيك . وهذا يجعل دالة أكرمان نقطة النهاية الأولى $f_{\omega }$ ضمن التسلسل الهرمي سريع النمو .

بعد نشر أكرمان ^{[ 2 ]} لدالته (التي تحتوي على ثلاثة وسائط صحيحة غير سالبة)، قام العديد من المؤلفين بتعديلها لتناسب أغراضًا مختلفة، بحيث يُمكن اليوم أن يُشير مصطلح "دالة أكرمان" إلى أيٍّ من المتغيرات العديدة للدالة الأصلية. أحد هذه المتغيرات الشائعة هو دالة أكرمان-بيتر ذات الوسيطين التي طورها روزا بيتر ورافائيل روبنسون . تُعرَّف هذه الدالة من خلال علاقة التكرار. $\operatorname {A} (m+1,n+1)=\operatorname {A} (m,\operatorname {A} (m+1,n))$ مع الحالات الأساسية المناسبة . وتزداد قيمتها بسرعة كبيرة؛ على سبيل المثال، $\operatorname {A} (4,2)$ النتائج في $2^{65536}-3$ ، عدد صحيح مكون من 19729 رقمًا عشريًا. ^{[ 3 ]}

تاريخ

في أواخر عشرينيات القرن العشرين، كان عالما الرياضيات غابرييل سودان وويلهلم أكرمان ، تلميذا ديفيد هيلبرت ، يدرسان أسس الحوسبة. يُنسب إلى كل من سودان وأكرمان ^{[ 4 ]} اكتشاف الدوال القابلة للحساب كليًا (والتي تُسمى ببساطة "التكرارية" في بعض المراجع) والتي لا تُعدّ تكرارية بدائية . نشر سودان دالته الأقل شهرة ، ثم بعد ذلك بفترة وجيزة وبشكل مستقل، في عام 1928، نشر أكرمان دالته. $\varphi$ (من اليونانية، الحرف فاي ). دالة أكرمان ذات الوسائط الثلاثة، $\varphi (m,n,p)$ ، يتم تعريفها بحيث يكون لـ $p=0,1,2$ فهو يعيد إنتاج العمليات الأساسية للجمع والضرب والأس كما

${\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,n,1)&=m\times n\\\varphi (m,n,2)&=m^{n}\end{aligned}}$

ولـ $p>2$ إنها توسع هذه العمليات الأساسية بطريقة يمكن مقارنتها بالعمليات الفائقة :

${\begin{aligned}\varphi (m,n,3)&=m[4](n+1)\\\varphi (m,n,p)&\gtrapprox m[p+1](n+1)&&{\text{for }}p>3\end{aligned}}$

(بصرف النظر عن دورها التاريخي كدالة قابلة للحساب الكلي ولكنها ليست بدائية متكررة، يُنظر إلى دالة أكرمان الأصلية على أنها توسع العمليات الحسابية الأساسية إلى ما وراء الأس، وإن لم يكن ذلك بسلاسة مثل متغيرات دالة أكرمان المصممة خصيصًا لهذا الغرض - مثل سلسلة العمليات الفائقة لجودستين .)

في كتابه "حول اللانهاية" ، ^{[ 5 ]} افترض ديفيد هيلبرت لأول مرة أن دالة أكرمان ليست دالة بدائية تكرارية، ولكن أكرمان، السكرتير الشخصي لهيلبرت وطالبه السابق، هو من أثبت هذه الفرضية في بحثه " حول بناء هيلبرت للأعداد الحقيقية" . ^{[ 2 ]}^{[ 6 ]}

قام كل من روزا بيتر ^{[ 7 ]} ورافائيل روبنسون ^{[ 8 ]} لاحقًا بتطوير نسخة ذات متغيرين من دالة أكرمان والتي أصبحت مفضلة لدى جميع المؤلفين تقريبًا.

متتالية العمليات الفائقة المعممة ، على سبيل المثال $G(m,a,b)=a[m]b$ ، وهي أيضاً نسخة من دالة أكرمان. ^{[ 9 ]}

في عام 1963، وضع ر. كريتون باك صيغة بديهية ذات متغيرين ^{[ n 1 ]} $\operatorname {F}$ حول تسلسل العمليات الفائقة : ^{[ 10 ]}^{[ 11 ]}

$\operatorname {F} (m,n)=2[m]n.$

بالمقارنة مع معظم الإصدارات الأخرى، لا تحتوي دالة باك على إزاحات غير ضرورية:

${\begin{aligned}\operatorname {F} (0,n)&=2[0]n=n+1\\\operatorname {F} (1,n)&=2[1]n=2+n\\\operatorname {F} (2,n)&=2[2]n=2\times n\\\operatorname {F} (3,n)&=2[3]n=2^{n}\\\operatorname {F} (4,n)&=2[4]n=2^{2^{2^{{}^{.^{.^{{}_{.}2}}}}}}\\&\quad \vdots \end{aligned}}$

تم بحث العديد من الصيغ الأخرى لدالة أكرمان. ^{[ 12 ]}^{[ 13 ]}

تعريف

التعريف: كدالة من الرتبة m

دالة أكرمان الأصلية ذات الوسائط الثلاثة $\varphi (m,n,p)$ يُعرَّف بشكل تكراري كما يلي للأعداد الصحيحة غير السالبة $m,n,$ و $p$ :

${\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,0,1)&=0\\\varphi (m,0,2)&=1\\\varphi (m,0,p)&=m&&{\text{for }}p>2\\\varphi (m,n,p)&=\varphi (m,\varphi (m,n-1,p),p-1)&&{\text{for }}n,p>0\end{aligned}}$

من بين النسخ المختلفة ذات الوسيطين، فإن النسخة التي طورها بيتر وروبنسون (والتي يطلق عليها معظم المؤلفين اسم دالة أكرمان) تُعرَّف للأعداد الصحيحة غير السالبة. $m$ و $n$ على النحو التالي:

${\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m+1,0)&=&\operatorname {A} (m,1)\\\operatorname {A} (m+1,n+1)&=&\operatorname {A} (m,\operatorname {A} (m+1,n))\end{array}}$

تم التعبير عن دالة أكرمان أيضًا فيما يتعلق بتسلسل العمليات الفائقة : ^{[ 14 ]}^{[ 15 ]}

$A(m,n)={\begin{cases}n+1&m=0\\2[m](n+3)-3&m>0\\\end{cases}}$

أو مكتوبة باستخدام تدوين كنوت للسهم العلوي (الممتد إلى مؤشرات الأعداد الصحيحة) $\geq -2$ ):

$A(m,n)={\begin{cases}n+1&m=0\\2\uparrow ^{m-2}(n+3)-3&m>0\\\end{cases}}$

أو، بشكل مكافئ، من حيث دالة باك F: ^{[ 10 ]}

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

بالحث على $m$ يمكن للمرء أن يثبت ذلك $F(m,n)\leq A(m,n)$ للجميع $m,n\in \mathbb {N} _{0}$ .

التعريف: كدالة أحادية متكررة

يُعرِّف $f^{n}$ باعتبارها التكرار رقم n من $f$ :

${\begin{array}{rll}f^{0}(x)&=&x\\f^{n+1}(x)&=&f(f^{n}(x))\end{array}}$

التكرار هو عملية دمج دالة مع نفسها عددًا معينًا من المرات. تركيب الدوال عملية تجميعية ، لذا $f(f^{n}(x))=f^{n}(f(x))$ .

بتصور دالة أكرمان كسلسلة من الدوال الأحادية، يمكن للمرء أن يضع $\operatorname {A} _{m}(n)=\operatorname {A} (m,n)$ .

ثم تصبح الدالة عبارة عن سلسلة $\operatorname {A} _{0},\operatorname {A} _{1},\operatorname {A} _{2},...$ من الدوال الأحادية ^{[ n 2 ]} ، المعرفة من التكرار :

${\begin{array}{lcl}\operatorname {A} _{0}(n)&=&n+1\\\operatorname {A} _{m+1}(n)&=&\operatorname {A} _{m}^{n+1}(1)\,.\end{array}}$

حساب

الحساب باستخدام برنامج LOOP

الوظائف $\operatorname {A} _{i}$ تتناسب مع التسلسل الهرمي سريع النمو (FGH) للوظائف (ذات المستوى المحدود) ^{[ 16 ]}

{\begin{array}{lcl}\operatorname {FGH} _{0}(n)&=&n+1\\\operatorname {FGH} _{m+1}(n)&=&\operatorname {FGH} _{m}^{n}(n)\,.\end{array}}

المتباينة التالية صحيحة: ^{[ 17 ]} $\forall m>1,\forall n>1:\operatorname {A} _{m}(n)<\operatorname {FGH} _{m}(n)$

للثابت $k$ ، الوظيفة $\operatorname {FGH} _{k}(n)$ يمكن حسابها بواسطة برنامج حلقة تكرارية بعمق تداخل $k$ [ ¹⁸^]

# إدخال (ن) حلقة ن : # عمق التداخل: 1 حلقة ن : # عمق التداخل: 2 ... # ... حلقة ن : # عمق التداخل: ك ن += 1 # # إخراج (ن)

الوظيفة $\operatorname {A} _{k}(n)$ يمكن أيضًا حسابها بواسطة برنامج LOOP-k. ^{[ 19 ]} (البرنامج (المخطط) غير مدرج هنا.)

من الواضح أن $\operatorname {A} (m,n)$ ، لكونها ليست دالة تكرارية بدائية - انظر أدناه - ، لا يمكن حسابها بواسطة برنامج LOOP.

الحساب عن طريق نظام إعادة كتابة المصطلحات، استنادًا إلى دالة ثنائية.

يمكن تحويل التعريف التكراري لدالة أكرمان بشكل طبيعي إلى نظام إعادة كتابة المصطلحات (TRS) .

يؤدي تعريف دالة أكرمان الثنائية إلى قواعد الاختزال الواضحة ^{[ 20 ]}^{[ 21 ]}

${\begin{array}{lll}{\text{(r1)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r2)}}&A(S(m),0)&\rightarrow &A(m,S(0))\\{\text{(r3)}}&A(S(m),S(n))&\rightarrow &A(m,A(S(m),n))\end{array}}$

مثال

الحوسبة $A(1,2)\rightarrow _{*}4$

تسلسل الاختزال هو ^{[ n 3 ]}

استراتيجية الخطوة الواحدة (من اليسار إلى الخارج) :	استراتيجية من اليسار إلى الداخل (خطوة واحدة) :
${\underline {A(S(0),S(S(0)))}}$	${\underline {A(S(0),S(S(0)))}}$
$\rightarrow _{r3}{\underline {A(0,A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,{\underline {A(S(0),S(0))}})$
$\rightarrow _{r1}S({\underline {A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,A(0,{\underline {A(S(0),0)}}))$
$\rightarrow _{r3}S({\underline {A(0,A(S0,0))}})$	$\rightarrow _{r2}A(0,A(0,{\underline {A(0,S(0))}}))$
$\rightarrow _{r1}S(S({\underline {A(S(0),0)}}))$	$\rightarrow _{r1}A(0,{\underline {A(0,S(S(0)))}})$
$\rightarrow _{r2}S(S({\underline {A(0,S(0))}}))$	$\rightarrow _{r1}{\underline {A(0,S(S(S(0))))}}$
$\rightarrow _{r1}S(S(S(S(0))))$	$\rightarrow _{r1}S(S(S(S(0))))$

لحساب $\operatorname {A} (m,n)$ يمكن استخدام مكدس ، والذي يحتوي في البداية على العناصر $\langle m,n\rangle$ .

ثم يتم استبدال العنصرين العلويين بشكل متكرر وفقًا للقواعد ^{[ ن 4 ]}

${\begin{array}{lllllllll}{\text{(r1)}}&0&,&n&\rightarrow &(n+1)\\{\text{(r2)}}&(m+1)&,&0&\rightarrow &m&,&1\\{\text{(r3)}}&(m+1)&,&(n+1)&\rightarrow &m&,&(m+1)&,&n\end{array}}$

بشكل تخطيطي، بدءًا من $\langle m,n\rangle$ :

طالما أن طول المكدس لا يساوي 1 { قم بإزالة عنصرين؛ ثم قم بدفع عنصر واحد أو عنصرين أو ثلاثة عناصر، مع تطبيق القواعد r1 و r2 و r3 }

تم نشر الشفرة الزائفة في Grossman & Zeitman (1988) .

على سبيل المثال، عند الإدخال $\langle 2,1\rangle$ ،

تكوينات المكدس	يعكس التخفيض ^{[ ن 5 ]}
${\underline {2,1}}$	${\underline {A(2,1)}}$
$\rightarrow 1,{\underline {2,0}}$	$\rightarrow _{r1}A(1,{\underline {A(2,0)}})$
$\rightarrow 1,{\underline {1,1}}$	$\rightarrow _{r2}A(1,{\underline {A(1,1)}})$
$\rightarrow 1,0,{\underline {1,0}}$	$\rightarrow _{r3}A(1,A(0,{\underline {A(1,0)}}))$
$\rightarrow 1,0,{\underline {0,1}}$	$\rightarrow _{r2}A(1,A(0,{\underline {A(0,1)}}))$
$\rightarrow 1,{\underline {0,2}}$	$\rightarrow _{r1}A(1,{\underline {A(0,2)}})$
$\rightarrow {\underline {1,3}}$	$\rightarrow _{r1}{\underline {A(1,3)}}$
$\rightarrow 0,{\underline {1,2}}$	$\rightarrow _{r3}A(0,{\underline {A(1,2)}})$
$\rightarrow 0,0,{\underline {1,1}}$	$\rightarrow _{r3}A(0,A(0,{\underline {A(1,1)}}))$
$\rightarrow 0,0,0,{\underline {1,0}}$	$\rightarrow _{r3}A(0,A(0,A(0,{\underline {A(1,0)}})))$
$\rightarrow 0,0,0,{\underline {0,1}}$	$\rightarrow _{r2}A(0,A(0,A(0,{\underline {A(0,1)}})))$
$\rightarrow 0,0,{\underline {0,2}}$	$\rightarrow _{r1}A(0,A(0,{\underline {A(0,2)}}))$
$\rightarrow 0,{\underline {0,3}}$	$\rightarrow _{r1}A(0,{\underline {A(0,3)}})$
$\rightarrow {\underline {0,4}}$	$\rightarrow _{r1}{\underline {A(0,4)}}$
$\rightarrow 5$	$\rightarrow _{r1}5$

ملاحظات

يتم تطبيق استراتيجية أقصى اليسار إلى الداخل في 225 لغة برمجة على برنامج Rosetta Code .
للجميع $m,n$ حساب $A(m,n)$ لا يستغرق الأمر أكثر من $(A(m,n)+1)^{m}$ خطوات. ^{[ 22 ]}
أشار غروسمان وزيتمان (1988) إلى أنه في حساب $\operatorname {A} (m,n)$ أقصى طول للكومة هو $\operatorname {A} (m,n)$ طالما $m>0$ .
تقوم خوارزميتهم الخاصة، وهي بطبيعتها تكرارية، بحساب $\operatorname {A} (m,n)$ داخل ${\mathcal {O}}(m\operatorname {A} (m,n))$ في الوقت وخلال ${\mathcal {O}}(m)$ فضاء.

الحساب بواسطة TRS، استنادًا إلى دالة أحادية متكررة

يؤدي تعريف دوال أكرمان أحادية الرتبة المتكررة إلى قواعد اختزال مختلفة

${\begin{array}{lll}{\text{(r4)}}&A(S(0),0,n)&\rightarrow &S(n)\\{\text{(r5)}}&A(S(0),S(m),n)&\rightarrow &A(S(n),m,S(0))\\{\text{(r6)}}&A(S(S(x)),m,n)&\rightarrow &A(S(0),m,A(S(x),m,n))\end{array}}$

بما أن تركيب الدوال ترابطي، فبدلاً من القاعدة r6 يمكن تعريف

${\begin{array}{lll}{\text{(r7)}}&A(S(S(x)),m,n)&\rightarrow &A(S(x),m,A(S(0),m,n))\end{array}}$

كما هو الحال في القسم السابق، فإن حساب $\operatorname {A} _{m}^{1}(n)$ يمكن تنفيذ ذلك باستخدام مكدس.

في البداية، تحتوي المجموعة على العناصر الثلاثة $\langle 1,m,n\rangle$ .

ثم يتم استبدال العناصر الثلاثة العلوية بشكل متكرر وفقًا للقواعد ^{[ ن 4 ]}

${\begin{array}{lllllllll}{\text{(r4)}}&1&,0&,n&\rightarrow &(n+1)\\{\text{(r5)}}&1&,(m+1)&,n&\rightarrow &(n+1)&,m&,1\\{\text{(r6)}}&(x+2)&,m&,n&\rightarrow &1&,m&,(x+1)&,m&,n\\\end{array}}$

بشكل تخطيطي، بدءًا من $\langle 1,m,n\rangle$ :

طالما أن طول المكدس لا يساوي 1 { قم بإزالة 3 عناصر؛ قم بدفع عنصر واحد أو 3 أو 5 عناصر، مع تطبيق القواعد r4 و r5 و r6؛ }

مثال

عند الإدخال $\langle 1,2,1\rangle$ تكون تكوينات المكدس المتتالية هي

${\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r6}1,1,{\underline {1,1,1}}\rightarrow _{r5}1,1,{\underline {2,0,1}}\rightarrow _{r6}1,1,1,0,{\underline {1,0,1}}\\&\rightarrow _{r4}1,1,{\underline {1,0,2}}\rightarrow _{r4}{\underline {1,1,3}}\rightarrow _{r5}{\underline {4,0,1}}\rightarrow _{r6}1,0,{\underline {3,0,1}}\rightarrow _{r6}1,0,1,0,{\underline {2,0,1}}\\&\rightarrow _{r6}1,0,1,0,1,0,{\underline {1,0,1}}\rightarrow _{r4}1,0,1,0,{\underline {1,0,2}}\rightarrow _{r4}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}$

المعادلات المقابلة هي

${\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}(A_{0}^{3}(1))=A_{0}(A_{0}(A_{0}^{2}(1)))\\&=A_{0}(A_{0}(A_{0}(A_{0}(1))))=A_{0}(A_{0}(A_{0}(2)))=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}$

عند استخدام قاعدة الاختزال r7 بدلاً من القاعدة r6، ستتبع عمليات الاستبدال في المكدس ما يلي:

${\begin{array}{lllllllll}{\text{(r7)}}&(x+2)&,m&,n&\rightarrow &(x+1)&,m&,1&,m&,n\end{array}}$

ستكون تكوينات المكدس المتتالية بعد ذلك

${\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r7}1,1,{\underline {1,1,1}}\rightarrow _{r5}1,1,{\underline {2,0,1}}\rightarrow _{r7}1,1,1,0,{\underline {1,0,1}}\\&\rightarrow _{r4}1,1,{\underline {1,0,2}}\rightarrow _{r4}{\underline {1,1,3}}\rightarrow _{r5}{\underline {4,0,1}}\rightarrow _{r7}3,0,{\underline {1,0,1}}\rightarrow _{r4}{\underline {3,0,2}}\\&\rightarrow _{r7}2,0,{\underline {1,0,2}}\rightarrow _{r4}{\underline {2,0,3}}\rightarrow _{r7}1,0,{\underline {1,0,3}}\rightarrow _{r4}{\underline {1,0,4}}\rightarrow _{r4}5\end{aligned}}$

المعادلات المقابلة هي

${\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}^{3}(A_{0}(1))=A_{0}^{3}(2)\\&=A_{0}^{2}(A_{0}(2))=A_{0}^{2}(3)=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}$

ملاحظات

عند أي مدخلات معينة، تتقارب أنظمة الاستجابة الزمنية (TRSs) المعروضة حتى الآن في نفس عدد الخطوات. كما أنها تستخدم نفس قواعد الاختزال (في هذه المقارنة، تُعتبر القواعد r1 و r2 و r3 "مماثلة" للقواعد r4 و r5 و r6/r7 على التوالي). على سبيل المثال، اختزال $A(2,1)$ يتقارب في 14 خطوة: 6 × r1، 3 × r2، 5 × r3. اختزال $A_{2}(1)$ يتقارب في نفس الخطوات الـ 14: 6 × r4، 3 × r5، 5 × r6/r7. تختلف خوارزميات TRS في ترتيب تطبيق قواعد الاختزال.
متى $A_{i}(n)$ يتم حسابها وفقًا للقواعد {r4، r5، r6}، ويبقى الحد الأقصى لطول المكدس أقل من $2\times A(i,n)$ عند استخدام قاعدة الاختزال r7 بدلاً من القاعدة r6، يكون الحد الأقصى لطول المكدس هو فقط $2(i+2)$ يعكس طول المكدس عمق الاستدعاء الذاتي. وبما أن الاختزال وفقًا للقواعد {r4، r5، r7} يتضمن عمق استدعاء ذاتي أقصى أصغر، ^{[ n 6 ]} فإن هذه العملية الحسابية أكثر كفاءة من هذه الناحية.

الحساب بواسطة TRS، استنادًا إلى المؤثرات الفائقة

كما أوضح سوندبلاد (1971) - أو بورتو وماتوس (1980) - بشكل صريح، يمكن التعبير عن دالة أكرمان من حيث متتالية العمليات الفائقة :

$A(m,n)={\begin{cases}n+1&m=0\\2[m](n+3)-3&m>0\\\end{cases}}$

أو، بعد إزالة الثابت 2 من قائمة المعاملات، بدلالة دالة باك

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

وظيفة باك $\operatorname {F} (m,n)=2[m]n$ ، ^{[ 10 ]} يمكن حساب أحد أشكال دالة أكرمان بمفردها باستخدام قواعد الاختزال التالية:

${\begin{array}{lll}{\text{(b1)}}&F(S(0),0,n)&\rightarrow &S(n)\\{\text{(b2)}}&F(S(0),S(0),0)&\rightarrow &S(S(0))\\{\text{(b3)}}&F(S(0),S(S(0)),0)&\rightarrow &0\\{\text{(b4)}}&F(S(0),S(S(S(m))),0)&\rightarrow &S(0)\\{\text{(b5)}}&F(S(0),S(m),S(n))&\rightarrow &F(S(n),m,F(S(0),S(m),0))\\{\text{(b6)}}&F(S(S(x)),m,n)&\rightarrow &F(S(0),m,F(S(x),m,n))\end{array}}$ بدلاً من القاعدة ب6، يمكن تعريف القاعدة

${\begin{array}{lll}{\text{(b7)}}&F(S(S(x)),m,n)&\rightarrow &F(S(x),m,F(S(0),m,n))\end{array}}$ لحساب دالة أكرمان، يكفي إضافة ثلاث قواعد اختزال.

${\begin{array}{lll}{\text{(r8)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r9)}}&A(S(m),n)&\rightarrow &P(F(S(0),S(m),S(S(S(n)))))\\{\text{(r10)}}&P(S(S(S(m))))&\rightarrow &m\\\end{array}}$

تتولى هذه القواعد معالجة الحالة الأساسية $A(0,n)$ ، المحاذاة $(n+3)$ والفدج (-3).

مثال

الحوسبة $A(2,1)\rightarrow _{*}5$

باستخدام قاعدة الاختزال ${\text{b7}}$ : ^{[ رقم 5 ]}	باستخدام قاعدة الاختزال ${\text{b6}}$ : ^{[ رقم 5 ]}
${\underline {A(2,1)}}$	${\underline {A(2,1)}}$
$\rightarrow _{r9}P({\underline {F(1,2,4)}})$	$\rightarrow _{r9}P({\underline {F(1,2,4)}})$
$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$	$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$
$\rightarrow _{b3}P({\underline {F(4,1,0)}})$	$\rightarrow _{b3}P({\underline {F(4,1,0)}})$
$\rightarrow _{b7}P(F(3,1,{\underline {F(1,1,0)}}))$	$\rightarrow _{b6}P(F(1,1,{\underline {F(3,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(3,1,2)}})$	$\rightarrow _{b6}P(F(1,1,F(1,1,{\underline {F(2,1,0)}})))$
$\rightarrow _{b7}P(F(2,1,{\underline {F(1,1,2)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,1,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b5}P(F(2,1,F(2,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(1,1,2)}})))$
$\rightarrow _{b2}P(F(2,1,{\underline {F(2,0,2)}}))$	$\rightarrow _{b5}P(F(1,1,F(1,1,F(2,0,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b7}P(F(2,1,F(1,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(2,0,2)}})))$
$\rightarrow _{b1}P(F(2,1,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,0,{\underline {F(1,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(2,1,4)}})$	$\rightarrow _{b1}P(F(1,1,F(1,1,{\underline {F(1,0,3)}})))$
$\rightarrow _{b7}P(F(1,1,{\underline {F(1,1,4)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,1,4)}}))$
$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$
$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$	$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$
$\rightarrow _{b7}P(F(1,1,F(3,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,{\underline {F(3,0,2)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(3,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,{\underline {F(2,0,2)}}))))$
$\rightarrow _{b7}P(F(1,1,F(2,0,{\underline {F(1,0,3)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}})))))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(2,0,4)}}))$	$\rightarrow _{b1}P(F(1,1,F(1,0,F(1,0,{\underline {F(1,0,3)}}))))$
$\rightarrow _{b7}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$	$\rightarrow _{b1}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$
$\rightarrow _{b1}P({\underline {F(1,1,6)}})$	$\rightarrow _{b1}P({\underline {F(1,1,6)}})$
$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$	$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(6,0,2)}})$	$\rightarrow _{b2}P({\underline {F(6,0,2)}})$
$\rightarrow _{b7}P(F(5,0,{\underline {F(1,0,2)}}))$	$\rightarrow _{b6}P(F(1,0,{\underline {F(5,0,2)}}))$
$\rightarrow _{b1}P({\underline {F(5,0,3)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,{\underline {F(4,0,2)}})))$
$\rightarrow _{b7}P(F(4,0,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,{\underline {F(3,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(4,0,4)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(2,0,2)}})))))$
$\rightarrow _{b7}P(F(3,0,{\underline {F(1,0,4)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}}))))))$
$\rightarrow _{b1}P({\underline {F(3,0,5)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,3)}})))))$
$\rightarrow _{b7}P(F(2,0,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,{\underline {F(1,0,4)}}))))$
$\rightarrow _{b1}P({\underline {F(2,0,6)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,{\underline {F(1,0,5)}})))$
$\rightarrow _{b7}P(F(1,0,{\underline {F(1,0,6)}}))$	$\rightarrow _{b1}P(F(1,0,{\underline {F(1,0,6)}}))$
$\rightarrow _{b1}P({\underline {F(1,0,7)}})$	$\rightarrow _{b1}P({\underline {F(1,0,7)}})$
$\rightarrow _{b1}{\underline {P(8)}}$	$\rightarrow _{b1}{\underline {P(8)}}$
$\rightarrow _{r10}5$	$\rightarrow _{r10}5$

المعادلات المتطابقة هي

عندما يكون نظام TRS مع قاعدة التخفيض ${\text{b6}}$ يتم تطبيق ما يلي:

${\begin{aligned}&A(2,1)+3=F(2,4)=\dots =F^{6}(0,2)=F(0,F^{5}(0,2))=F(0,F(0,F^{4}(0,2)))\\&=F(0,F(0,F(0,F^{3}(0,2))))=F(0,F(0,F(0,F(0,F^{2}(0,2)))))=F(0,F(0,F(0,F(0,F(0,F(0,2))))))\\&=F(0,F(0,F(0,F(0,F(0,3)))))=F(0,F(0,F(0,F(0,4))))=F(0,F(0,F(0,5)))=F(0,F(0,6))=F(0,7)=8\end{aligned}}$

عندما يكون نظام TRS مع قاعدة التخفيض ${\text{b7}}$ يتم تطبيق ما يلي:

${\begin{aligned}&A(2,1)+3=F(2,4)=\dots =F^{6}(0,2)=F^{5}(0,F(0,2))=F^{5}(0,3)=F^{4}(0,F(0,3))=F^{4}(0,4)\\&=F^{3}(0,F(0,4))=F^{3}(0,5)=F^{2}(0,F(0,5))=F^{2}(0,6)=F(0,F(0,6))=F(0,7)=8\end{aligned}}$ ملاحظات

حساب $\operatorname {A} _{i}(n)$ وفقًا للقواعد {b1 - b5, b6, r8 - r10}، فإن التداخل عميق. أقصى عمق للتداخل $F$ s هو $A(i,n)+1$ يكمن السبب في ترتيب تنفيذ التكرار: $F^{n+1}(x)=F(F^{n}(x))$ . الأول $F$ لا يختفي إلا بعد اكتمال التسلسل بأكمله.
تُعدّ الحسابات وفقًا للقواعد {b1 - b5, b7, r8 - r10} أكثر كفاءة من هذه الناحية. التكرار $F^{n+1}(x)=F^{n}(F(x))$ يحاكي هذا البرنامج حلقة التكرار على كتلة من التعليمات البرمجية. ^{[ n 7 ]} يقتصر التداخل على $(i+1)$ مستوى واحد من التكرار لكل دالة متكررة. وقد أظهر ماير وريتشي (1967) هذه العلاقة.
تتعلق هذه الاعتبارات بعمق الاستدعاء الذاتي فقط. تؤدي كلتا طريقتي التكرار إلى نفس عدد خطوات الاختزال، وتتضمن نفس القواعد (عندما تُعتبر القاعدتان b6 و b7 "متماثلتين"). اختزال $A(2,1)$ على سبيل المثال، يتقارب في 35 خطوة: 12 × b1، 4 × b2، 1 × b3، 4 × b5، 12 × b6/b7، 1 × r9، 1 × r10. يؤثر modus iterandi فقط على ترتيب تطبيق قواعد الاختزال.
لا يمكن تحقيق مكسب حقيقي في وقت التنفيذ إلا بتجنب إعادة حساب النتائج الفرعية مرارًا وتكرارًا. التخزين المؤقت هو أسلوب تحسين يتم فيه تخزين نتائج استدعاءات الدوال مؤقتًا وإعادتها عند تكرار نفس المدخلات. انظر على سبيل المثال Ward (1993) . نشر Grossman & Zeitman (1988) خوارزمية ذكية لحساب $A(i,n)$ داخل ${\mathcal {O}}(iA(i,n))$ في الوقت وخلال ${\mathcal {O}}(i)$ فضاء.

أعداد هائلة

لتوضيح كيفية حساب $A(4,3)$ ينتج عنه العديد من الخطوات وعدد كبير: ^{[ n 5 ]}

${\begin{aligned}A(4,3)&\rightarrow A(3,A(4,2))\\&\rightarrow A(3,A(3,A(4,1)))\\&\rightarrow A(3,A(3,A(3,A(4,0))))\\&\rightarrow A(3,A(3,A(3,A(3,1))))\\&\rightarrow A(3,A(3,A(3,A(2,A(3,0)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(2,1)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(2,0))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(1,1))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,3)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(1,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,2)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,3))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,4)))))\\&\rightarrow A(3,A(3,A(3,A(2,5))))\\&\qquad \vdots \\&\rightarrow A(3,A(3,A(3,13)))\\&\qquad \vdots \\&\rightarrow A(3,A(3,65533))\\&\qquad \vdots \\&\rightarrow A(3,2^{65536}-3)\\&\qquad \vdots \\&\rightarrow 2^{2^{65536}}-3.\\\end{aligned}}$

جدول القيم

يمكن إعادة صياغة حساب دالة أكرمان باستخدام جدول لانهائي. أولًا، ضع الأعداد الطبيعية على طول الصف العلوي. لتحديد عدد في الجدول، خذ العدد الموجود مباشرةً على يساره. ثم استخدم هذا العدد للبحث عن العدد المطلوب في العمود الذي يحمل هذا العدد والصف الذي يليه. إذا لم يكن هناك عدد على يساره، فانظر ببساطة إلى العمود الذي يحمل الرقم "1" في الصف السابق. إليك جزء صغير من أعلى يسار الجدول:

قيم A ( m , n )
ن م	0	1	2	3	4	ن
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2=2+(n+3)-3$
2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13	65533	2 ⁶⁵⁵³⁶ – 3	${2^{2^{65536}}}-3$	${2^{2^{2^{65536}}}}-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} _{n+3}-3\end{matrix}}$
			$=2\uparrow \uparrow 5-3$ $\approx 2.00353\cdot {10^{19728}}$	$=2\uparrow \uparrow 6-3$	$=2\uparrow \uparrow 7-3$
				$=2\uparrow \uparrow 6-3$	$=2\uparrow \uparrow 7-3$	$=2\uparrow \uparrow (n+3)-3$
5	65533	$2\uparrow \uparrow 65536-3$	$2\uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow (n+3)-3$
6	$2\uparrow \uparrow 65536-3$	$2\uparrow \uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow \uparrow (n+3)-3$
م	$(2\uparrow ^{m-2}3)-3$	$(2\uparrow ^{m-2}4)-3$	$(2\uparrow ^{m-2}5)-3$	$(2\uparrow ^{m-2}6)-3$	$(2\uparrow ^{m-2}7)-3$	$(2\uparrow ^{m-2}(n+3))-3$

الأرقام هنا التي يتم التعبير عنها فقط باستخدام الأس المتكرر أو أسهم كنوت كبيرة جدًا وستشغل مساحة كبيرة جدًا بحيث لا يمكن تدوينها بأرقام عشرية عادية.

على الرغم من القيم الكبيرة الواردة في هذا الجزء المبكر من الجدول، فقد تم تعريف بعض الأعداد الأكبر، مثل عدد غراهام ، الذي لا يمكن كتابته باستخدام عدد قليل من أسهم كنوت. يُبنى هذا العدد بتقنية مشابهة لتطبيق دالة أكرمان على نفسها بشكل متكرر.

هذا تكرار للجدول أعلاه، ولكن مع استبدال القيم بالتعبير ذي الصلة من تعريف الدالة لإظهار النمط بوضوح:

قيم A ( m , n )
ن م	0	1	2	3	4	ن
0	0+1	1+1	2+1	3+1	4+1	ن + 1
1	أ (0، 1)	A (0, A (1, 0)) = A (0, 2)	A (0, A (1, 1)) = A (0, 3)	A (0, A (1, 2)) = A (0, 4)	A (0, A (1, 3)) = A (0, 5)	A (0, A (1, n −1))
2	أ (1، 1)	A (1, A (2, 0)) = A (1, 3)	A (1, A (2, 1)) = A (1, 5)	A (1, A (2, 2)) = A (1, 7)	A (1, A (2, 3)) = A (1, 9)	A (1, A (2, n −1))
3	أ (2، 1)	A (2, A (3, 0)) = A (2, 5)	A (2, A (3, 1)) = A (2, 13)	A (2, A (3, 2)) = A (2, 29)	A (2, A (3, 3)) = A (2, 61)	A (2, A (3, n −1))
4	أ (3، 1)	A (3, A (4, 0)) = A (3, 13)	A (3, A (4, 1)) = A (3, 65533)	A (3, A (4, 2))	A (3, A (4, 3))	A (3, A (4, n −1))
5	أ (4، 1)	A (4, A (5, 0))	A (4, A (5, 1))	A (4, A (5, 2))	A (4, A (5, 3))	A (4, A (5, n −1))
6	أ (5، 1)	A (5, A (6, 0))	A (5, A (6, 1))	A (5, A (6, 2))	A (5, A (6, 3))	A (5, A (6, n −1))

ملكيات

ملاحظات عامة

قد لا يكون من الواضح على الفور أن تقييم $A(m,n)$ تنتهي العملية دائمًا. ومع ذلك، فإن الاستدعاء الذاتي محدود لأنه في كل تطبيق استدعاء ذاتي إما $m$ يتناقص، أو $m$ يبقى كما هو و $n$ يتناقص. في كل مرة يحدث ذلك $n$ يصل إلى الصفر، $m$ يتناقص، لذلك $m$ يصل في النهاية إلى الصفر أيضًا. (بتعبير أدق، في كل حالة الزوج $(m,n)$ يتناقص الترتيب المعجمي على الأزواج، وهو ترتيب جيد ، تمامًا مثل ترتيب الأعداد الصحيحة غير السالبة المفردة؛ وهذا يعني أنه لا يمكن النزول في الترتيب عددًا لا نهائيًا من المرات المتتالية. ومع ذلك، عندما $m$ لا يوجد حد أقصى لمقدار الانخفاض $n$ يمكن أن يزداد - وغالباً ما سيزداد بشكل كبير.
بالنسبة للقيم الصغيرة لـ m مثل 1 أو 2 أو 3، تنمو دالة أكرمان ببطء نسبيًا بالنسبة لـ n ( بشكل أسي على الأكثر ). $m\geq 4$ إلا أنها تنمو بسرعة أكبر بكثير؛ حتى $A(4,2)$ يساوي حوالي 2.00353 × 10^{19728 ،} والتوسع العشري لـ $A(4,3)$ وهو كبير جدًا بأي مقياس نموذجي، حوالي 2.12004 × 10 ^{6.03123 × 10¹⁹⁷²⁷} .
من الجوانب المثيرة للاهتمام أن العملية الحسابية الوحيدة التي يستخدمها هي جمع 1. وتعتمد قدرته المتنامية بسرعة على الاستدعاء الذاتي المتداخل فقط. وهذا يعني أيضاً أن وقت تشغيله يتناسب على الأقل مع ناتجه، وبالتالي فهو ضخم للغاية. في الواقع، في معظم الحالات يكون وقت التشغيل أكبر بكثير من الناتج؛ انظر أعلاه.
نسخة ذات وسيط واحد $f(n)=A(n,n)$ وهذا يزيد من كليهما $m$ و $n$ في الوقت نفسه، يتفوق هذا على كل دالة تكرارية بدائية، بما في ذلك الدوال سريعة النمو للغاية مثل الدالة الأسية ، ودالة المضروب، ودوال المضروب المتعدد والمضروب الفائق ، وحتى الدوال المعرفة باستخدام تدوين سهم كنوت الصاعد (باستثناء استخدام السهم الصاعد المفهرس). ويمكن ملاحظة ذلك. $f(n)$ وهو ما يعادل تقريبًا $f_{\omega }(n)$ في التسلسل الهرمي سريع النمو . يمكن استغلال هذا النمو الهائل لإظهار أن $f$ ، والتي من الواضح أنها قابلة للحساب على جهاز ذي ذاكرة لا نهائية مثل آلة تورينج وبالتالي فهي دالة قابلة للحساب ، تنمو بشكل أسرع من أي دالة تكرارية بدائية وبالتالي فهي ليست تكرارية بدائية.

ليس بدائيًا تكراريًا

تنمو دالة أكرمان بشكل أسرع من أي دالة تكرارية بدائية ، وبالتالي فهي ليست دالة تكرارية بدائية بحد ذاتها.

رسم توضيحي :

تُبنى الدوال التكرارية الأولية من الدوال الأساسية باستخدام التركيب والتكرار الأولي، وتنمو جميعها ضمن معدل معين. نُعرّف، بشكل بنائي، تسلسلًا هرميًا للدوال الكلية. $\operatorname {FGH} _{k}(n)$ بواسطة:

$\operatorname {FGH} _{0}(n)=n+1,\quad \operatorname {FGH} _{k+1}(n)=\operatorname {FGH} _{k}^{n}(n)$

أين $\operatorname {FGH} _{k}^{n}$ يشير $n$ تكرار ذو -ط $\operatorname {FGH} _{k}$ عند الإدخال $n$ [ ²³^{] ينمو هذا التسلسل}^الهرمي بشكل أسرع مع ازدياد $k$ وكل دالة تكرارية أولية تكون محدودة في النهاية من الأعلى بواسطة شيء ما $\operatorname {FGH} _{k}$ ويمكن إثبات ذلك عن طريق الاستقراء البنيوي . على تعريفات الدوال التكرارية الأولية.

ومع ذلك، فإن دالة أكرمان $\operatorname {A} (m,n)$ وفي النهاية يتجاوز كل $\operatorname {FGH} _{k}$ لكل $k$ ، يوجد $m$ بحيث $\operatorname {A} (m,n)>\operatorname {FGH} _{k}(n)$ لجميع الأحجام الكبيرة بما فيه الكفاية $n$ . هكذا، $\operatorname {A}$ ينمو بشكل أسرع من أي دالة تكرارية بدائية، وبالتالي فهو ليس دالة تكرارية بدائية.

معكوس

بما أن الدالة f ( n ) = A ( n , n ) المذكورة أعلاه تنمو بسرعة كبيرة، فإن دالتها العكسية f⁻¹ تنمو ببطء شديد. يُرمز عادةً إلى دالة أكرمان العكسية f⁻¹ بالرمز α . في الواقع، α ( n ) أقل من 5 لأي حجم إدخال عملي n ، لأن A (4, 4) ^من رتبة 5 ^. $2^{2^{2^{2^{16}}}}$ .

يظهر هذا العكس في التعقيد الزمني لبعض الخوارزميات، مثل بنية بيانات المجموعة المنفصلة وخوارزمية شازيل للأشجار الممتدة الدنيا . أحيانًا تُستخدم دالة أكرمان الأصلية أو صيغ أخرى منها في هذه الحالات، لكنها جميعًا تنمو بمعدلات عالية مماثلة. على وجه الخصوص، تُبسط بعض الدوال المُعدلة التعبير بحذف الحد -3 وما شابهه.

يمكن تعريف صيغة متغيرة ذات معلَمين لدالة أكرمان العكسية على النحو التالي، حيث $\lfloor x\rfloor$ هل دالة الأرضية هي :

$\alpha (m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}.$

تظهر هذه الدالة في تحليلات أكثر دقة للخوارزميات المذكورة أعلاه، وتُعطي حدًا زمنيًا أدق. في بنية بيانات المجموعة المنفصلة، يُمثل m عدد العمليات بينما يُمثل n عدد العناصر؛ وفي خوارزمية الشجرة الممتدة الدنيا، يُمثل m عدد الحواف بينما يُمثل n عدد الرؤوس. توجد عدة تعريفات مختلفة قليلاً لـ α ( m , n ) ؛ على سبيل المثال، يُستبدل log₂n أحيانًا بـ n ، وتُستبدل دالة الجزء الصحيح أحيانًا بدالة الجزء الصحيح _. .

قد تُعرّف دراسات أخرى دالة عكسية للواحد حيث يتم تعيين m على قيمة ثابتة، بحيث ينطبق العكس على صف معين. ^{[ 24 ]}

إن معكوس دالة أكرمان هو دالة بدائية تكرارية، لأنه دالة بدائية تكرارية في الرسم البياني، وهو محدود من الأعلى بدالة بدائية تكرارية. ^{[ 25 ]}

الاستخدام

في التعقيد الحسابي

تظهر دالة أكرمان في التعقيد الزمني لبعض الخوارزميات ، ^{[ 26 ]} مثل أنظمة جمع المتجهات ^{[ 27 ]} وإمكانية الوصول لشبكة بيتري ، مما يدل على أنها غير مجدية حسابيًا للحالات الكبيرة. ^{[ 28 ]}

يظهر معكوس دالة أكرمان في بعض نتائج تعقيد الوقت. على سبيل المثال، تستغرق بنية بيانات المجموعة المنفصلة وقتًا مستهلكًا لكل عملية يتناسب مع معكوس دالة أكرمان، ^{[ 29 ]} ولا يمكن تسريعها ضمن نموذج مسبار الخلية لتعقيد الحساب. ^{[ 30 ]}

في الهندسة المنفصلة

توجد حدود تعقيد لبعض المسائل في الهندسة المتقطعة المتعلقة بمتتاليات دافنبورت-شينزل، حيث تكون دالة أكرمان العكسية $\alpha (n)$ يظهر. على سبيل المثال، لـ $n$ القطع المستقيمة في المستوى، والوجه غير المحدود لترتيب القطع يتميز بالتعقيد $O(n\alpha (n))$ وبعض أنظمة $n$ تتمتع القطع المستقيمة بمستوى تعقيد لا حدود له $\Omega (n\alpha (n))$ [ ³¹^]

كمعيار

تُعدّ دالة أكرمان، نظرًا لتعريفها القائم على الاستدعاء الذاتي العميق للغاية، معيارًا لقياس قدرة المُصرّف على تحسين الاستدعاء الذاتي. وقد نُشر أول استخدام لدالة أكرمان بهذه الطريقة عام 1970 بواسطة دراغوش فايدا ^{[ 32 ]} ، وفي الوقت نفسه تقريبًا، عام 1971، بواسطة ينجفي سوندبلاد ^{[ 14 ] .}

تم تناول ورقة سوندبلاد الرائدة من قبل برايان ويشمان (المؤلف المشارك لمعيار ويتستون ) في ثلاثية من الأوراق التي كتبت بين عامي 1975 و 1982. ^{[ 33 ]}^{[ 34 ]}^{[ 35 ]}

انظر أيضاً

ملحوظات

↑ مع عكس ترتيب المعلمات
↑ ' كاري '
↑ في كل خطوة، تتم إعادة كتابة النص الذي تحته خط.
1 2 هنا: استراتيجية من اليسار إلى الداخل!
1 2 3 4 لتحسين سهولة القراءة، يُرمز إلى S(0) بالرقم 1،ويُرمز إلى S(S(0)) بالرقم 2،ويُرمز إلى S(S(S(0))) بالرقم 3،وهكذا...
↑ يشير أقصى عمق للتكرار إلى عدد مستويات تفعيل الإجراء الموجودة خلال أعمق استدعاء له. كورنيليوس وكيربي (1975)
↑ كرر n+1 مرة كرر F

مراجع

^ مونين وهينشي 2003 ، ص. 61.
1 2 أكرمان 1928 .
↑ "التوسيع العشري للعدد A(4,2)" . kosara.net . 27 أغسطس 2000. مؤرشف من الأصل في 20 يناير 2010.
↑ كالود، ماركوس وتيفي 1979 .
↑ هيلبرت 1926 ، ص 185.
↑ فان هيجينورت 1977 .
↑ بيتر 1935 .
↑ روبنسون 1948 .
↑ ريتشي 1965 ، ص 1028.
1 2 3 باك 1963 .
^ ميوسن وزانتيما 1992 ، ص. 6.
↑ مونافو 1999أ .
↑ ريتشي 1965 .
1 2 Sundblad 1971 .
↑ بورتو وماتوس 1980 .
↑ أوديفردي 1999 ، ص 298.
↑ "التسلسل الهرمي لأكرمان مقابل التسلسل الهرمي سريع النمو" . StackExchange .
↑
المسافة البادئة وفقًا لقاعدة التجاوز ( INDENT ... DEDENT )، كما هو الحال في بايثون :
```
for _ in range ( n ): n += 1
```
↑ ماير وريتشي 1967 .
↑ غروسمان وزيتمان 1988 .
↑ بولسون 2021 .
↑ كوهين 1987 ، ص 56، الاقتراح 3.16 (انظر في البرهان).
↑ سلسلة أخرى من الدوال، $\operatorname {E} _{n}$ يُستخدم تعريف التسلسل الهرمي لغريغورتشيك بشكل متكرر لتقسيم الدوال التكرارية الأولية إلى "فئات نمو". ومع ذلك، $\operatorname {FGH} _{n}$ (أو $\operatorname {A} _{n}$ ) و $\operatorname {E} _{n}$ لا تتوافق في فهرسة البيانات الخاصة بها.
↑ بيتي 2002 .
↑ ماتوس 2014 .
↑ بروبيكر 2023 .
^ تشيروينسكي وأورليكوفسكي 2022 .
↑ ليرو 2022 .
↑ تارجان 1975 .
↑ فريدمان وساكس 1989 .
↑ ويرنيك وشارير 1988 .
↑ فايدا 1970 .
↑ ويشمان 1976 .
↑ ويشمان 1977 .
↑ ويشمان 1982 .

فهرس

أكرمان، فيلهلم (1928). "Zum Hilbertschen Aufbau der reellen Zahlen" [ حول البناء الهيلبرتي للأعداد الحقيقية ] . Mathematische Annalen (باللغة الألمانية). 99 : 118 – 133. دوى : 10.1007 / BF01459088 . S2CID 123431274 .
باك، آر سي (1963). "الاستقراء الرياضي والتعريفات التكرارية". المجلة الرياضية الأمريكية الشهرية . 70 (2): 128-135 . doi : 10.2307/2312881 . JSTOR 2312881 .
كالود، كريستيان ؛ ماركوس، سولومون ؛ تيفي، أيونيل (نوفمبر 1979). "المثال الأول لدالة تكرارية ليست تكرارية بدائية" . هيستوريا ماث. 6 (4): 380-384 . doi : 10.1016/0315-0860(79)90024-7 .
كوهين، دانيال إي. (يناير 1987). الحوسبة والمنطق . دار هالستيد للنشر. ISBN 9780745800349.
كورنيليوس، بي جيه؛ كيربي، جي إتش (1975). "عمق الاستدعاء الذاتي ودالة أكرمان". مجلة الرياضيات العددية BIT . 15 (2): 144-150 . doi : 10.1007/BF01932687 . S2CID 120532578 .
تشيرفينسكي، فويتش؛ أورليكوفسكي، لوكاس (7 فبراير 2022). إمكانية الوصول في أنظمة جمع المتجهات هي مسألة أكرمان-كاملة . وقائع الندوة السنوية الثانية والستين لمؤسسة مهندسي الكهرباء والإلكترونيات لعام 2021 حول أسس علوم الحاسوب. arXiv : 2104.13866 . doi : 10.1109/FOCS52979.2021.00120 .
فريدمان، م.؛ ساكس، م. (مايو 1989). "تعقيد مسبار الخلية لهياكل البيانات الديناميكية". وقائع الندوة السنوية الحادية والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '89 . الصفحات 345-354 . doi : 10.1145/73007.73040 . ISBN 0897913078. S2CID 13470414 .
جروسمان، جيرولد دبليو؛ زيتمان، آر. سوزان (مايو 1988). "حساب تكراري بطبيعته لدالة أكرمان". علوم الحاسوب النظرية . 57 ( 2-3 ): 327-330 . doi : 10.1016/0304-3975(88)90046-1 .
فان هيجينورت، جان (1977) [أعيد طبعه مع تصحيحات، نُشر لأول مرة عام 1967]. من فريجه إلى غودل: كتاب مصادر في المنطق الرياضي، 1879-1931 . مطبعة جامعة هارفارد.
هيلبرت، ديفيد (1926). "Über das Unendliche" [ في اللانهائية ] . Mathematische Annalen (باللغة الألمانية). 95 : 161– 190. دوى : 10.1007/BF01206605 . S2CID 121888793 .
ليرو، جيروم (7 فبراير 2022). مشكلة الوصول لشبكات بيتري ليست بدائية تكرارية . وقائع الندوة السنوية الثانية والستين لمؤسسة مهندسي الكهرباء والإلكترونيات لعام 2021 حول أسس علوم الحاسوب. arXiv : 2104.12695 . doi : 10.1109/FOCS52979.2021.00121 .
لوب، MH. وينر، سس (1970). “التسلسلات الهرمية للوظائف النظرية للأرقام. أنا.” . أرشيف المنطق الرياضي و Grundlagenforschung . 13 ( 1 – 2): 39 – 51. دوى : 10.1007 / BF01967649 .
ماتوس، أرماندو ب (7 مايو 2014). "معكوس دالة أكرمان بدائي تكراري" (ملف PDF) . مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022.
ميوسن، ف.س.؛ زانتيما، هـ. (1992). أطوال الاشتقاق في إعادة كتابة المصطلحات من التفسيرات في الأعداد الطبيعية (ملف PDF) (تقرير). قسم علوم الحاسوب، جامعة أوتريخت. الرقم الدولي الموحد للدوريات 0924-3275 . مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022.
ماير، ألبرت ر .؛ ريتشي، دينيس ماكاليستر (1967). "تعقيد برامج الحلقات". وقائع المؤتمر الوطني الثاني والعشرين لعام 1967. ACM '67: وقائع المؤتمر الوطني الثاني والعشرين لعام 1967. الصفحات 465-469 . doi : 10.1145/800196.806014 .
مونين، جان فرانسوا؛ هينشي، إم جي (2003). فهم الأساليب الرسمية . سبرينغر. ص 61. ISBN 9781852332471.
مونافو، روبرت (1999أ). "صيغ دالة أكرمان" . الأعداد الكبيرة في MROB . تم الاسترجاع في 6 نوفمبر 2021 .
مونافو، روبرت (1999ب). "ابتكار عوامل ووظائف جديدة" . الأعداد الكبيرة في MROB . تم الاسترجاع في 6 نوفمبر 2021 .
أوديفردي، بييرجيورجيو (1999). نظرية الاستدعاء الذاتي الكلاسيكية. المجلد الثاني . دراسات في المنطق وأسس الرياضيات. المجلد 143. أمستردام: نورث هولاند. ISBN 978-0-444-50205-6MR 1718169 .
بولسون، لورانس سي. (2021). "دالة أكرمان في شكل تكراري: تجربة مساعدة في البرهان" . تم الاسترجاع في 19 أكتوبر 2021 .
بيتر روزا (1935). "Konstruktion nichtrekursiver Funktionen" [إنشاء وظائف غير متكررة ] . Mathematische Annalen (باللغة الألمانية). 111 : 42 – 60. دوى : 10.1007 / BF01472200 . S2CID 121107217 .
بيتي، س. (2002). "حد أدنى على غرار أكرمان العكسي لمسألة التحقق من الشجرة الممتدة الدنيا عبر الإنترنت". وقائع الندوة السنوية الثالثة والأربعين لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، 2002. الصفحات 155-163 . doi : 10.1109/SFCS.2002.1181892 . ISBN 0-7695-1822-2. S2CID 8636108 .
بورتو، أنطونيو؛ ماتوس، أرماندو ب. (1 سبتمبر 1980). " أكرمان والقوى العظمى" (ملف PDF) . أخبار ACM SIGACT . 12 (3): 90-95 . doi : 10.1145/1008861.1008872 . S2CID 29780652. مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022.النسخة الأصلية 1980، نُشرت في ACM SIGACT News ، وتم تعديلها في 20 أكتوبر 2012 و23 يناير 2016 (ورقة عمل)
ريتشي، روبرت ويلز (نوفمبر 1965). "فئات الدوال التكرارية القائمة على دالة أكرمان" . مجلة المحيط الهادئ للرياضيات . 15 (3): 1027-1044 . doi : 10.2140/pjm.1965.15.1027 .
روبنسون، رافائيل ميتشل (1948). "الاستدعاء الذاتي والاستدعاء الذاتي المزدوج" . نشرة الجمعية الرياضية الأمريكية . 54 (10): 987-993 . doi : 10.1090/S0002-9904-1948-09121-2 .
سوندبلاد، ينجفي (مارس 1971). "دالة أكرمان: دراسة نظرية وحسابية وصيغية". مجلة BIT للرياضيات العددية . 11 (1): 107-119 . doi : 10.1007/BF01935330 . S2CID 123416408 .
تارجان، روبرت إندري (1975). "كفاءة خوارزمية اتحاد مجموعات جيدة ولكنها غير خطية". مجلة ACM . 22 (2): 215-225 . doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 .
فايدا، دراجوس (1970). “التحقق من صحة المترجم للغة تشبه Algol”. نشرة Mathématique de la Société des Sciences Mathématiques de la République Socialiste de Romanie . مسلسل جديد. 14 (62) (4): 487- 502. جستور 43679758 .
وينر، سس (1970). “تصنيف للوظائف العودية الترتيبية”. أرشيف المنطق الرياضي و Grundlagenforschung . 13 ( 3– 4): 136– 153. دوى : 10.1007 / bf01973619 .
وارد، مارتن ب. (16 يوليو 1993). إجراءات تكرارية لحساب دالة أكرمان . CiteSeerX 10.1.1.35.9907 .
ويشمان، برايان أ. (مارس 1976). "دالة أكرمان: دراسة في كفاءة استدعاء الإجراءات". مجلة BIT للرياضيات العددية . 16 : 103-110 . CiteSeerX 10.1.1.108.4125 . doi : 10.1007/BF01940783 . S2CID 16993343 .
ويشمان، برايان أ. (يوليو 1977). "كيفية استدعاء الإجراءات، أو إعادة النظر في دالة أكرمان". مجلة BIT للرياضيات العددية . 16 (3): 103-110 . doi : 10.1002/spe.4380070303 . S2CID 206507320 .
ويشمان، برايان أ. (يوليو 1982). "أحدث نتائج اختبار استدعاء الإجراءات، دالة أكرمان" (ملف PDF) . مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022.

روابط خارجية

"دالة أكرمان" . موسوعة الرياضيات . مطبعة EMS . 2001 [1994].
وايسشتاين، إريك دبليو. "دالة أكرمان" . عالم الرياضيات .
تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "دالة أكرمان" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .
آلة حاسبة متحركة لدالة أكرمان
آرونسون، سكوت (1999). "من يستطيع تسمية الرقم الأكبر؟" .
دوال أكرمان . تتضمن جدولاً لبعض القيم.
بروباكر، بن (4 ديسمبر 2023). "مشكلة تبدو سهلة تؤدي إلى أرقام أكبر من أن يستوعبها كوننا" .
مونافو، روبرت. "الأعداد الكبيرة" .يصف عدة اختلافات في تعريف A.
نيفاش، غابرييل (أكتوبر 2021). "أكرمان المعكوس بدون ألم" . مؤرشف من الأصل في 21 أغسطس 2007. تم الاطلاع عليه في 18 يونيو 2023 .
سيدل، رايموند. "فهم دالة أكرمان العكسية" (PDF) .
دالة أكرمان مكتوبة بلغات برمجة مختلفة (على برنامج Rosetta Code ).
سميث، هاري ج. "دالة أكرمان" . مؤرشف من الأصل في 26 أكتوبر 2009.بعض الدراسة والبرمجة.
فيرنيك، آدي؛ شارير، ميشا (1988). "التحقيقات المستوية لمتتاليات دافنبورت-شينزل غير الخطية بواسطة القطع" . الهندسة المنفصلة والحسابية . 3 (1): 15-47 . doi : 10.1007/BF02187894 . MR 0918177 .

[letop3-10] مع عكس ترتيب المعلمات

[letop4-17] ' كاري '

[letop5-24] في كل خطوة، تتم إعادة كتابة النص الذي تحته خط.

[letop2-25] 1 2 هنا: استراتيجية من اليسار إلى الداخل!

[letop1-26] 1 2 3 4 لتحسين سهولة القراءة، يُرمز إلى S(0) بالرقم 1،ويُرمز إلى S(S(0)) بالرقم 2،ويُرمز إلى S(S(S(0))) بالرقم 3،وهكذا...

[letop6-28] يشير أقصى عمق للتكرار إلى عدد مستويات تفعيل الإجراء الموجودة خلال أعمق استدعاء له. كورنيليوس وكيربي (1975)

[letop7-29] كرر n+1 مرة كرر F

[FOOTNOTEMoninHinchey200361-1] مونين وهينشي 2003 ، ص. 61.

[FOOTNOTEAckermann1928-2] 1 2 أكرمان 1928 .

[3] "التوسيع العشري للعدد A(4,2)" . kosara.net . 27 أغسطس 2000. مؤرشف من الأصل في 20 يناير 2010.

[FOOTNOTECaludeMarcusTevy1979-4] كالود، ماركوس وتيفي 1979 .

[FOOTNOTEHilbert1926185-5] هيلبرت 1926 ، ص 185.

[FOOTNOTEvan_Heijenoort1977-6] فان هيجينورت 1977 .

[FOOTNOTEPéter1935-7] بيتر 1935 .

[FOOTNOTERobinson1948-8] روبنسون 1948 .

[FOOTNOTERitchie19651028-9] ريتشي 1965 ، ص 1028.

[FOOTNOTEBuck1963-11] 1 2 3 باك 1963 .

[FOOTNOTEMeeussenZantema19926-12] ميوسن وزانتيما 1992 ، ص. 6.

[FOOTNOTEMunafo1999a-13] مونافو 1999أ .

[FOOTNOTERitchie1965-14] ريتشي 1965 .

[FOOTNOTESundblad1971-15] 1 2 Sundblad 1971 .

[FOOTNOTEPortoMatos1980-16] بورتو وماتوس 1980 .

[FOOTNOTEOdifreddi1999298-18] أوديفردي 1999 ، ص 298.

[19] "التسلسل الهرمي لأكرمان مقابل التسلسل الهرمي سريع النمو" . StackExchange .

[20] المسافة البادئة وفقًا لقاعدة التجاوز ( INDENT ... DEDENT )، كما هو الحال في بايثون :
for _ in range ( n ): n += 1

[FOOTNOTEMeyerRitchie1967-21] ماير وريتشي 1967 .

[FOOTNOTEGrossmanZeitman1988-22] غروسمان وزيتمان 1988 .

[FOOTNOTEPaulson2021-23] بولسون 2021 .

[FOOTNOTECohen198756Proposition_3.16_(see_in_proof)-27] كوهين 1987 ، ص 56، الاقتراح 3.16 (انظر في البرهان).

[30] سلسلة أخرى من الدوال، $\operatorname {E} _{n}$ يُستخدم تعريف التسلسل الهرمي لغريغورتشيك بشكل متكرر لتقسيم الدوال التكرارية الأولية إلى "فئات نمو". ومع ذلك، $\operatorname {FGH} _{n}$ (أو $\operatorname {A} _{n}$ ) و $\operatorname {E} _{n}$ لا تتوافق في فهرسة البيانات الخاصة بها.

[FOOTNOTEPettie2002-31] بيتي 2002 .

[FOOTNOTEMatos2014-32] ماتوس 2014 .

[FOOTNOTEBrubaker2023-33] بروبيكر 2023 .

[FOOTNOTECzerwińskiOrlikowski2022-34] تشيروينسكي وأورليكوفسكي 2022 .

[FOOTNOTELeroux2022-35] ليرو 2022 .

[FOOTNOTETarjan1975-36] تارجان 1975 .

[FOOTNOTEFredmanSaks1989-37] فريدمان وساكس 1989 .

[FOOTNOTEWiernikSharir1988-38] ويرنيك وشارير 1988 .

[FOOTNOTEVaida1970-39] فايدا 1970 .

[FOOTNOTEWichmann1976-40] ويشمان 1976 .

[FOOTNOTEWichmann1977-41] ويشمان 1977 .

[FOOTNOTEWichmann1982-42] ويشمان 1982 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ n 1 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ n 2 ]

[ 16 ]

[ 17 ]

18

[ 19 ]

[ 20 ]

[ 21 ]

[ n 3 ]

[ ن 4 ]

[ ن 5 ]

[ 22 ]

[ n 6 ]

[ n 7 ]

23

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

31

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗