एकरमैन समारोह

This article is about the mathematical function. For other uses, see Ackermann (disambiguation).

कम्प्यूटेबिलिटी संगणनीयता सिद्धांत, विल्हेम एकरमैन के नाम पर एकरमैन फ़ंक्शन, सबसे सरल में से एक है और कुल फ़ंक्शन गणना योग्य समारोह के शुरुआती-खोजे गए उदाहरण जो आदिम पुनरावर्ती फ़ंक्शन नहीं हैं। सभी आदिम पुनरावर्ती कार्य कुल और संगणनीय हैं, लेकिन एकरमैन फ़ंक्शन यह दर्शाता है कि सभी कुल संगणनीय कार्य आदिम पुनरावर्ती नहीं हैं। एकरमैन के प्रकाशन के बाद अपने कार्य के (जिसमें तीन गैर-नकारात्मक पूर्णांक तर्क थे), कई लेखकों ने इसे विभिन्न उद्देश्यों के अनुरूप संशोधित किया, ताकि आज एकरमैन फ़ंक्शन मूल फ़ंक्शन के कई रूपों में से किसी को भी संदर्भित कर सके। एक सामान्य संस्करण, दो-तर्क एकरमैन-पीटर फ़ंक्शन को गैर-नकारात्मक पूर्णांक 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}}$

छोटे इनपुट के लिए भी इसका मूल्य तेजी से बढ़ता है। उदाहरण के लिए, A(4, 2) 19,729 दशमलव अंकों का एक पूर्णांक है (2 के बराबर⁶⁵⁵³⁶−3, या 2²²²²−3).

इतिहास

1920 के दशक के अंत में, गणितज्ञ गेब्रियल सूडान और विल्हेम एकरमैन, डेविड हिल्बर्ट के छात्र, संगणना की नींव का अध्ययन कर रहे थे। सूडान और एकरमैन दोनों को श्रेय दिया जाता है कुल फ़ंक्शन कंप्यूटेबल फ़ंक्शंस की खोज के साथ (जिसे कुछ संदर्भों में केवल रिकर्सिव कहा जाता है) जो आदिम रिकर्सिव फ़ंक्शन नहीं हैं। सूडान ने कम प्रसिद्ध सूडान कार्य प्रकाशित किया, फिर कुछ ही समय बाद और स्वतंत्र रूप से, 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}}$

(कुल-गणना योग्य-लेकिन-नहीं-आदिम-पुनरावर्ती कार्य के रूप में इसकी ऐतिहासिक भूमिका के अलावा, एकरमैन के मूल कार्य को घातांक से परे बुनियादी अंकगणितीय संचालन का विस्तार करने के लिए देखा जाता है, हालांकि एकरमैन के फ़ंक्शन के रूपांतरों के समान नहीं है जो विशेष रूप से डिज़ाइन किए गए हैं। वह उद्देश्य - जैसे रूबेन गुडस्टीन|गुडस्टीन का हाइपरऑपरेशन अनुक्रम।)

अनंत पर में, डेविड हिल्बर्ट ने परिकल्पना की कि एकरमैन फ़ंक्शन आदिम पुनरावर्ती नहीं था, लेकिन यह एकरमैन, हिल्बर्ट के निजी सचिव और पूर्व छात्र थे, जिन्होंने वास्तव में अपने पेपर ऑन हिल्बर्ट्स कंस्ट्रक्शन ऑफ़ द रियल नंबर्स में परिकल्पना को साबित किया था।

पीटर रोजसा और राफेल रॉबिन्सन ने बाद में एकरमैन फ़ंक्शन का एक दो-चर संस्करण विकसित किया जो लगभग सभी लेखकों द्वारा पसंद किया गया।

सामान्यीकृत हाइपरऑपरेशन, उदा। $G(m,a,b)=a[m]b$, एकरमैन फ़ंक्शन का भी एक संस्करण है।

1963 में रॉबर्ट क्रेटन बक|आर.सी. बक एक सहज ज्ञान युक्त दो-चर आधारित है प्रकार $\operatorname {F}$ हाइपरऑपरेशन पर:

$\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}}$

एकरमैन फ़ंक्शन के कई अन्य संस्करणों की जांच की गई है।

परिभाषा

=== परिभाषा: एम-एरी फ़ंक्शन === के रूप में एकरमैन का मूल तीन-तर्क कार्य $\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,A(m+1,n))\end{array}}$

हाइपरऑपरेशन के संबंध में एकरमेन फ़ंक्शन भी व्यक्त किया गया है:

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

या, नुथ के अप-एरो नोटेशन में लिखा गया है (पूर्णांक सूचकांकों तक विस्तारित $\geq -2$):

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

या, समतुल्य रूप से, बक के फलन F के संदर्भ में:

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

=== परिभाषा: पुनरावृत्त 1-एरी फ़ंक्शन === के रूप में परिभाषित करना $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},...$ यूनरी का फ़ंक्शंस, इटरेटेड फ़ंक्शन से परिभाषित:

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

संगणना

एकरमैन फ़ंक्शन की पुनरावर्ती परिभाषा को स्वाभाविक रूप से पुनर्लेखन | टर्म पुनर्लेखन प्रणाली (TRS) में स्थानांतरित किया जा सकता है।

=== टीआरएस, 2-एरी फ़ंक्शन === पर आधारित है 2-ary एकरमैन फ़ंक्शन की परिभाषा स्पष्ट कमी नियमों की ओर ले जाती है

${\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$ घटाव क्रम है

Leftmost-outermost (one-step) strategy:	Leftmost-innermost (one-step) strategy:
${\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$.

फिर बार-बार दो शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है

${\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
{
   पीओपी 2 तत्व;
   PUSH 1 या 2 या 3 तत्व, नियमों को लागू करते हुए r1, r2, r3
}

स्यूडोकोड प्रकाशित हो चुकी है। Grossman & Zeitman (1988).

उदाहरण के लिए, इनपुट पर $\langle 2,1\rangle$,

the stack configurations	reflect the reduction
${\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 कंप्यूटर भाषाओं में सबसे वामपंथी-अंतरतम रणनीति लागू की गई है।
• सभी के लिए $m,n$ की गणना $A(m,n)$ से अधिक नहीं लेता है $(A(m,n)+1)^{m}$ कदम।
• Grossman & Zeitman (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)$ अंतरिक्ष।

=== टीआरएस, पुनरावृत्त 1-एरी फ़ंक्शन === पर आधारित है पुनरावृत्त 1-ary एकरमैन फ़ंक्शन की परिभाषा विभिन्न कमी नियमों की ओर ले जाती है

${\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$.

फिर बार-बार तीन शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है:${\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 तत्व;
   पुश 1 या 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}}$

जब नियम r6 के बजाय कमी नियम r7 का उपयोग किया जाता है, तो स्टैक में प्रतिस्थापन का पालन किया जाएगा

${\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}}$

टिप्पणियां

• किसी दिए गए इनपुट पर अब तक प्रस्तुत टीआरएस समान चरणों में अभिसरण करते हैं। वे समान कटौती नियमों का भी उपयोग करते हैं (इस तुलना में नियमों 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। टीआरएस उस क्रम में भिन्न होते हैं जिसमें कटौती नियम लागू होते हैं।
• कब $A_{i}(n)$ {r4, r5, r6} नियमों का पालन करते हुए गणना की जाती है, स्टैक की अधिकतम लंबाई नीचे रहती है $2\times A(i,n)$. जब नियम r6 के स्थान पर कमी नियम r7 का उपयोग किया जाता है, तो स्टैक की अधिकतम लंबाई केवल होती है $2(i+2)$. ढेर की लंबाई रिकर्सन गहराई को दर्शाती है। नियमों के अनुसार कमी के रूप में {r4, r5, r7} में पुनरावर्तन की एक छोटी अधिकतम गहराई शामिल है, यह गणना उस संबंध में अधिक कुशल है।

टीआरएस, हाइपरऑपरेटरों पर आधारित

जैसा Sundblad (1971) - या Porto & Matos (1980) - स्पष्ट रूप से दिखाया गया है, एकरमैन फ़ंक्शन हाइपरऑपरेशन अनुक्रम के संदर्भ में व्यक्त किया जा सकता है:

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

या, बक के कार्य के संदर्भ में, पैरामीटर सूची से निरंतर 2 को हटाने के बाद

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

बक का कार्य $\operatorname {F} (m,n)=2[m]n$, अपने आप में एकरमैन फ़ंक्शन का एक प्रकार, निम्न कमी नियमों के साथ गणना की जा सकती है:

${\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}}$

नियम b6 के स्थान पर नियम को परिभाषित किया जा सकता है

${\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}}$

ये नियम बेस केस ए (0, एन), संरेखण (एन + 3) और फज (-3) का ख्याल रखते हैं।

उदाहरण

गणना करना $A(2,1)\rightarrow _{*}5$

using reduction rule ${\text{b7}}$:	using reduction rule ${\text{b6}}$:
${\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$

मिलान करने वाली समानताएं हैं

• जब टीआरएस कटौती नियम के साथ ${\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}}$

• जब टीआरएस कटौती नियम के साथ ${\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)$ नियमों के मुताबिक {बी 1 - बी 5, बी 6, आर 8 - आर 10} गहरा रिकर्सिव है। नेस्टेड की अधिकतम गहराई $F$एस है $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))$ कोड के एक ब्लॉक पर बार-बार लूप को सिम्युलेट करता है। घोंसला बनाना तक सीमित है $(i+1)$, प्रति पुनरावृत्त कार्य के लिए एक पुनरावर्तन स्तर। Meyer & Ritchie (1967) ने यह पत्राचार दिखाया।
• ये विचार केवल पुनरावर्तन गहराई से संबंधित हैं। पुनरावृति का कोई भी तरीका समान नियमों को शामिल करते हुए समान संख्या में कटौती चरणों की ओर ले जाता है (जब नियम b6 और b7 को समान माना जाता है)। की कमी $A(2,1)$ उदाहरण के लिए 35 चरणों में परिवर्तित होता है: 12 × b1, 4 × b2, 1 × b3, 4 × b5, 12 × b6/b7, 1 × r9, 1 × r10। कार्यप्रणाली केवल उस क्रम को प्रभावित करती है जिसमें कटौती नियम लागू होते हैं।
• निष्पादन समय का वास्तविक लाभ बार-बार उप-परिणामों की पुनर्गणना न करके ही प्राप्त किया जा सकता है। संस्मरण एक ऑप्टिमाइज़ेशन तकनीक है जहाँ फ़ंक्शन कॉल के परिणाम कैश किए जाते हैं और उसी इनपुट के फिर से आने पर वापस आ जाते हैं। उदाहरण के लिए देखें Ward (1993). Grossman & Zeitman (1988) ने एक चालाक एल्गोरिदम प्रकाशित किया जो गणना करता है $A(i,n)$ अंदर ${\mathcal {O}}(iA(i,n))$ समय और भीतर ${\mathcal {O}}(i)$ अंतरिक्ष।

बड़ी संख्या

यह प्रदर्शित करने के लिए कि की गणना कैसे की जाती है $A(4,3)$ कई चरणों में और बड़ी संख्या में परिणाम:

${\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 वाले कॉलम को देखें। यहाँ तालिका का एक छोटा ऊपरी-बाएँ भाग है:

Values of A(m, n)

n m	0	1	2	3	4	n
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 $={2^{2^{2}}}-3$ $=2\uparrow \uparrow 3-3$	65533 $={2^{2^{2^{2}}}}-3$ $=2\uparrow \uparrow 4-3$	265536 − 3 $={2^{2^{2^{2^{2}}}}}-3$ $=2\uparrow \uparrow 5-3$	${2^{2^{65536}}}-3$ $={2^{2^{2^{2^{2^{2}}}}}}-3$ $=2\uparrow \uparrow 6-3$	${2^{2^{2^{65536}}}}-3$ $={2^{2^{2^{2^{2^{2^{2}}}}}}}-3$ $=2\uparrow \uparrow 7-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} _{n+3}-3\end{matrix}}$ $=2\uparrow \uparrow (n+3)-3$
5	65533 $=2\uparrow \uparrow (2\uparrow \uparrow 2)-3$ $=2\uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow 4-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 \uparrow \uparrow 3-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$
m	$(2\to 3\to (m-2))-3$	$(2\to 4\to (m-2))-3$	$(2\to 5\to (m-2))-3$	$(2\to 6\to (m-2))-3$	$(2\to 7\to (m-2))-3$	$(2\to (n+3)\to (m-2))-3$

यहां संख्याएं जो केवल रिकर्सिव एक्सपोनेंटिएशन या नुथ के अप-एरो नोटेशन के साथ व्यक्त की जाती हैं, बहुत बड़ी हैं और सादे दशमलव अंकों में नोट करने के लिए बहुत अधिक जगह लेती हैं।

तालिका के इस प्रारंभिक खंड में बड़े मूल्यों के होने के बावजूद, कुछ और भी बड़ी संख्याओं को परिभाषित किया गया है, जैसे ग्राहम की संख्या, जिसे किसी भी छोटी संख्या में नूथ तीरों के साथ नहीं लिखा जा सकता है। यह संख्या एक ऐसी तकनीक के साथ बनाई गई है जो एकरमेन फ़ंक्शन को पुनरावर्ती रूप से लागू करने के समान है।

यह उपरोक्त तालिका का दोहराव है, लेकिन पैटर्न को स्पष्ट रूप से दिखाने के लिए फ़ंक्शन परिभाषा से प्रासंगिक अभिव्यक्ति द्वारा प्रतिस्थापित मानों के साथ:

Values of A(m, n)

n m	0	1	2	3	4	n
0	0+1	1+1	2+1	3+1	4+1	n + 1
1	A(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	A(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	A(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	A(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	A(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	A(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$ बढ़ सकता है - और यह अक्सर बहुत बढ़ जाएगा।
• 1, 2, या 3 जैसे m के छोटे मानों के लिए, एकरमैन फ़ंक्शन n के संबंध में अपेक्षाकृत धीमी गति से बढ़ता है (अधिकतम घातीय वृद्धि पर)। के लिए $m\geq 4$हालाँकि, यह बहुत अधिक तेज़ी से बढ़ता है; यहां तक ​​की $A(4,2)$ लगभग 2 है×10¹⁹⁷²⁸, और का दशमलव विस्तार $A(4,3)$ किसी भी विशिष्ट माप से बहुत बड़ा है।
• एक दिलचस्प पहलू यह है कि इसका उपयोग करने वाला एकमात्र अंकगणितीय ऑपरेशन 1 का योग है। इसकी तेजी से बढ़ती शक्ति पूरी तरह से नेस्टेड पुनरावर्तन पर आधारित है। इसका तात्पर्य यह भी है कि इसके चलने का समय कम से कम इसके उत्पादन के अनुपात में है, और यह भी बहुत बड़ा है। वास्तविकता में, ज्यादातर मामलों में चलने का समय आउटपुट से कहीं बड़ा होता है; ऊपर देखें।
• एक एकल-तर्क संस्करण $f(n)=A(n,n)$ जो दोनों को बढ़ाता है $m$ और $n$ एक ही समय में प्रत्येक आदिम पुनरावर्ती कार्य को बौना कर देता है, जिसमें बहुत तेजी से बढ़ने वाले कार्य शामिल हैं जैसे कि घातीय कार्य, बहुउद्देशीय कार्य, बहु- और superactorial कार्य, और यहां तक ​​​​कि Knuth के अप-एरो नोटेशन का उपयोग करके परिभाषित फ़ंक्शन (अनुक्रमित अप-एरो को छोड़कर) प्रयोग किया जाता है)। यह देखा जा सकता है $f(n)$ मोटे तौर पर तुलनीय है $f_{\omega }(n)$ तेजी से बढ़ते पदानुक्रम में। यह दिखाने के लिए इस चरम वृद्धि का फायदा उठाया जा सकता है $f$ जो स्पष्ट रूप से ट्यूरिंग मशीन जैसी अनंत मेमोरी वाली मशीन पर गणना योग्य है और इसलिए एक गणना योग्य कार्य है, किसी भी आदिम पुनरावर्ती कार्य की तुलना में तेजी से बढ़ता है और इसलिए आदिम पुनरावर्ती नहीं है।

=== आदिम पुनरावर्ती === नहीं

एकरमैन फ़ंक्शन किसी भी आदिम पुनरावर्ती फ़ंक्शन की तुलना में तेज़ी से बढ़ता है और इसलिए स्वयं आदिम पुनरावर्ती नहीं है। सबूत का स्केच यह है: k रिकर्सन तक का उपयोग करके परिभाषित एक आदिम पुनरावर्ती फ़ंक्शन की तुलना में धीमी गति से बढ़ना चाहिए $f_{k+1}(n)$, (k+1)-th फ़ंक्शन तेजी से बढ़ते पदानुक्रम में, लेकिन एकरमैन फ़ंक्शन कम से कम उतनी ही तेज़ी से बढ़ता है $f_{\omega }(n)$.

विशेष रूप से, एक दिखाता है कि प्रत्येक आदिम पुनरावर्ती कार्य के लिए $f(x_{1},\ldots ,x_{n})$ एक गैर-ऋणात्मक पूर्णांक मौजूद है $t$ जैसे कि सभी गैर-ऋणात्मक पूर्णांकों के लिए $x_{1},\ldots ,x_{n}$,

$f(x_{1},\ldots ,x_{n})<A(t,\max _{i}x_{i}).$

एक बार यह स्थापित हो जाने के बाद, यह उसका अनुसरण करता है $A$ स्वयं आदिम पुनरावर्ती नहीं है, अन्यथा डालने के बाद से $x_{1}=x_{2}=t$ विरोधाभास की ओर ले जाएगा $A(t,t)<A(t,t).$ प्रमाण इस प्रकार आगे बढ़ता है: वर्ग को परिभाषित करें ${\mathcal {A}}$ एकरमेन फ़ंक्शन की तुलना में धीमी गति से बढ़ने वाले सभी कार्यों में से

${\mathcal {A}}=\left\{f\,{\bigg |}\,\exists t\ \forall x_{1}\cdots \forall x_{n}:\ f(x_{1},\ldots ,x_{n})<A(t,\max _{i}x_{i})\right\}$

और दिखाओ ${\mathcal {A}}$ सभी आदिम पुनरावर्ती कार्य शामिल हैं। उत्तरार्द्ध इसे दिखाकर हासिल किया जाता है ${\mathcal {A}}$ इसमें निरंतर कार्य, उत्तराधिकारी कार्य, प्रक्षेपण कार्य शामिल हैं और यह कार्य रचना और आदिम पुनरावर्तन के संचालन के तहत बंद है।

उलटा

समारोह के बाद से {{nowrap|1= f(n) = A(n, n)}ऊपर माना गया } बहुत तेजी से बढ़ता है, इसका उलटा कार्य, f⁻¹, बहुत धीरे बढ़ता है। यह व्युत्क्रम एकरमैन फ़ंक्शन f⁻¹ को आमतौर पर α से दर्शाया जाता है। वास्तव में, α(n) किसी भी व्यावहारिक इनपुट आकार n के लिए 5 से कम है, क्योंकि A(4, 4) के आदेश पर है $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) अस्तित्व; उदाहरण के लिए, log₂ n को कभी-कभी n से बदल दिया जाता है, और फ़्लोर फ़ंक्शन को कभी-कभी छत समारोह से बदल दिया जाता है।

अन्य अध्ययन एक के व्युत्क्रम कार्य को परिभाषित कर सकते हैं जहां m एक स्थिरांक पर सेट है, जैसे कि व्युत्क्रम किसी विशेष पंक्ति पर लागू होता है।

एकरमैन फ़ंक्शन का व्युत्क्रम आदिम पुनरावर्ती है।

बेंचमार्क के रूप में प्रयोग करें

एकरमैन फ़ंक्शन, अत्यधिक गहरी रिकर्सन के संदर्भ में इसकी परिभाषा के कारण, रिकर्सन को अनुकूलित करने के लिए संकलक की क्षमता के बेंचमार्क के रूप में उपयोग किया जा सकता है। इस तरह से एकरमैन के कार्य का पहला प्रकाशित उपयोग 1970 में ड्रैगोस वैदा द्वारा किया गया था। और, लगभग साथ-साथ, 1971 में, येंगवे सुन्दब्लाड द्वारा।

1975 और 1982 के बीच लिखे गए पत्रों की एक त्रयी में ब्रायन विचमैन (वेटस्टोन (बेंचमार्क) के सह-लेखक) द्वारा सुंदरब्लैड का मौलिक पेपर लिया गया था।

यह भी देखें

• कम्प्यूटेबिलिटी सिद्धांत
• डबल रिकर्सन
• तेजी से बढ़ती पदानुक्रम
• गुडस्टीन समारोह
• आदिम पुनरावर्ती कार्य
• रिकर्सन (कंप्यूटर विज्ञान)

ग्रन्थसूची

• Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007/BF01459088. S2CID 123431274.
• Buck, R.C. (1963). "Mathematical Induction and Recursive Definitions". American Mathematical Monthly. 70 (2): 128–135. doi:10.2307/2312881. JSTOR 2312881.
• Calude, Cristian; Marcus, Solomon; Tevy, Ionel (November 1979). "The first example of a recursive function which is not primitive recursive". Historia Math. 6 (4): 380–84. doi:10.1016/0315-0860(79)90024-7.
• Cohen, Daniel E. (January 1987). Computability and logic. Halsted Press. ISBN 9780745800349.
• Cornelius, B.J.; Kirby, G.H. (1975). "Depth of recursion and the ackermann function". BIT Numerical Mathematics. 15 (2): 144–150. doi:10.1007/BF01932687. S2CID 120532578.
• Grossman, Jerrold W.; Zeitman, R.Suzanne (May 1988). "An inherently iterative computation of ackermann's function". Theoretical Computer Science. 57 (2–3): 327–330. doi:10.1016/0304-3975(88)90046-1.
• van Heijenoort, Jean (1977) [reprinted with corrections, first published in 1967]. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press.
• Hilbert, David (1926). "Über das Unendliche". Mathematische Annalen. 95: 161–190. doi:10.1007/BF01206605. S2CID 121888793.
• Matos, Armando B (May 7, 2014). "The inverse of the Ackermann function is primitive recursive" (PDF). Archived (PDF) from the original on 2022-10-09.
• Meeussen, V.C.S.; Zantema, H. (1992). Derivation lengths in term rewriting from interpretations in the naturals (PDF) (Report). Universiteit Utrecht. UU-CS, Department of Computer Science. ISSN 0924-3275. Archived (PDF) from the original on 2022-10-09.
• Meyer, Albert R.; Ritchie, Dennis MacAlistair (1967). "The complexity of loop programs". Proceedings of the 1967 22nd national conference. ACM '67: Proceedings of the 1967 22nd national conference. pp. 465–469. doi:10.1145/800196.806014.
• Monin, Jean-Francois; Hinchey, M. G. (2003). Understanding Formal Methods. Springer. p. 61. ISBN 9781852332471.
• Munafo, Robert (1999a). "Versions of Ackermann's Function". Large Numbers at MROB. Retrieved 2021-11-06.
• Munafo, Robert (1999b). "Inventing New Operators and Functions". Large Numbers at MROB. Retrieved 2021-11-06.
• Paulson, Lawrence C. (2021). "Ackermann's Function in Iterative Form: A Proof Assistant Experiment". Retrieved 2021-10-19.
• Péter, Rózsa (1935). "Konstruktion nichtrekursiver Funktionen". Mathematische Annalen. 111: 42–60. doi:10.1007/BF01472200. S2CID 121107217.
• Pettie, S. (2002). "An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem". The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings: 155–163. doi:10.1109/SFCS.2002.1181892. ISBN 0-7695-1822-2. S2CID 8636108.
• Porto, António; Matos, Armando B. (1 September 1980). "Ackermann and the superpowers" (PDF). ACM SIGACT News. 12 (3): Original version 1980, published in “ACM SIGACT News”, Modified in October 20, 2012, Modified in January 23, 2016 (working paper). doi:10.1145/1008861.1008872. S2CID 29780652. Archived (PDF) from the original on 2022-10-09.
• Ritchie, Robert Wells (November 1965). "Classes of recursive functions based on Ackermann's function". Pacific Journal of Mathematics. 15 (3): 1027–1044. doi:10.2140/pjm.1965.15.1027.
• Robinson, Raphael Mitchel (1948). "Recursion and Double Recursion". Bulletin of the American Mathematical Society. 54 (10): 987–93. doi:10.1090/S0002-9904-1948-09121-2.
• Sundblad, Yngve (March 1971). "The Ackermann function. A theoretical, computational, and formula manipulative study". BIT Numerical Mathematics. 11 (1): 107–119. doi:10.1007/BF01935330. S2CID 123416408.
• Vaida, Dragoș (1970). "Compiler Validation for an Algol-like Language". Bulletin Mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie. Nouvelle série. 14 (62) (4): 487–502. JSTOR 43679758.
• Ward, Martin P. (16 July 1993). Iterative Procedures for Computing Ackerman's Function. CiteSeerX 10.1.1.35.9907.
• Wichmann, Brian A. (March 1976). "Ackermann's function: A study in the efficiency of calling procedures". BIT Numerical Mathematics. 16: 103–110. doi:10.1007/BF01940783. S2CID 16993343.
• Wichmann, Brian A. (July 1977). "How to call procedures, or second thoughts on Ackermann's function". BIT Numerical Mathematics. 16 (3): 103–110. doi:10.1002/spe.4380070303. S2CID 206507320.
• Wichmann, Brian A. (July 1982). "Latest results from the procedure calling test, Ackermann's function" (PDF). Archived (PDF) from the original on 2022-10-09.

बाहरी संबंध

• "Ackermann function". Encyclopedia of Mathematics. EMS Press. 2001 [1994].
• Weisstein, Eric W. "Ackermann function". MathWorld.
•  This article incorporates public domain material from Black, Paul E. "Ackermann's function". Dictionary of Algorithms and Data Structures.
• An animated Ackermann function calculator
• Ackerman function implemented using a for loop
• Scott Aaronson, Who can name the biggest number? (1999)
• Ackermann functions. Includes a table of some values.
• Hyper-operations: Ackermann's Function and New Arithmetical Operation
• Robert Munafo's Large Numbers describes several variations on the definition of A.
• Gabriel Nivasch, Inverse Ackermann without pain on the inverse Ackermann function.
• Raimund Seidel, Understanding the inverse Ackermann function (PDF presentation).
• The Ackermann function written in different programming languages, (on Rosetta Code)
• Ackermann's Function (Archived 2009-10-24)—Some study and programming by Harry J. Smith.