एकरमैन फलन

कम्प्यूटेबिलिटी सिद्धांत में, विल्हेम एकरमैन के नाम पर एकरमैन फ़ंक्शन, सबसे सरल में से एक है^[1] और कुल फ़ंक्शन गणना योग्य समारोह के सबसे पहले खोजे गए उदाहरण जो आदिम पुनरावर्ती फ़ंक्शन नहीं हैं। सभी आदिम पुनरावर्ती कार्य कुल और संगणनीय हैं, लेकिन एकरमैन फ़ंक्शन यह दर्शाता है कि सभी कुल संगणनीय कार्य आदिम पुनरावर्ती नहीं हैं। एकरमैन के प्रकाशन के बाद^[2] उनके कार्य के (जिसमें तीन गैर-ऋणात्मक पूर्णांक तर्क थे), कई लेखकों ने इसे विभिन्न उद्देश्यों के अनुरूप संशोधित किया, ताकि आज एकरमैन फ़ंक्शन मूल फ़ंक्शन के कई रूपों में से किसी को भी संदर्भित कर सके। एक सामान्य संस्करण, दो-तर्क एकरमैन-पीटर फ़ंक्शन को गैर-नकारात्मक पूर्णांक 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 दशमलव अंकों का पूर्णांक है^[3] (2 के बराबर⁶⁵⁵³⁶−3, या 2^{2^{2^2²}}−3).

इतिहास

1920 के दशक के अंत में, गणितज्ञ गेब्रियल सूडान और विल्हेम एकरमैन, डेविड हिल्बर्ट के छात्र, संगणना की नींव का अध्ययन कर रहे थे। सूडान और एकरमैन दोनों को श्रेय दिया जाता है^[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]

परिभाषा

=== परिभाषा: एम-एरी फ़ंक्शन === के रूप में एकरमैन का मूल तीन-तर्क कार्य $\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}}

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

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 के संदर्भ में:^[10] :::

={\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))\,\,\,\,\{{\textrm {for}}\,\,n\geq 1\}\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}}

संगणना

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

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

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

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

फिर बार-बार दो शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है^{[n 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
{
   पीओपी 2 तत्व;
   PUSH 1 या 2 या 3 तत्व, नियमों को लागू करते हुए r1, r2, r3
}

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

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

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

फिर बार-बार तीन शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है^{[n 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 तत्व;
   पुश 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} में पुनरावर्तन की एक छोटी अधिकतम गहराई शामिल है,^{[n 6]} यह गणना उस संबंध में अधिक कुशल है।

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

जैसा 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$ ,^[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}}

नियम 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}}$ :^{[n 5]}	using reduction rule ${\text{b6}}$ :^{[n 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$

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

जब टीआरएस कटौती नियम के साथ ${\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, \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))$ कोड के एक ब्लॉक पर बार-बार लूप को सिम्युलेट करता है।^{[n 7]} घोंसला बनाना तक सीमित है $(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)$ कई चरणों में और बड़ी संख्या में परिणाम:^{[n 5]}

\begin{aligned} A (4, 3) & \to A (3, A (4, 2)) \\ \to A (3, A (3, A (4, 1))) \\ \to A (3, A (3, A (3, A (4, 0)))) \\ \to A (3, A (3, A (3, A (3, 1)))) \\ \to A (3, A (3, A (3, A (2, A (3, 0))))) \\ \to A (3, A (3, A (3, A (2, A (2, 1))))) \\ \to A (3, A (3, A (3, A (2, A (1, A (2, 0)))))) \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$	2⁶⁵⁵³⁶ − 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).$ सबूत^[18] निम्नानुसार आगे बढ़ता है: वर्ग को परिभाषित करें ${\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}}$ इसमें निरंतर कार्य, उत्तराधिकारी कार्य, प्रक्षेपण कार्य शामिल हैं और यह कार्य रचना और आदिम पुनरावर्तन के संचालन के तहत बंद है।

उलटा

समारोह के बाद से 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 एक स्थिरांक पर सेट है, जैसे कि व्युत्क्रम किसी विशेष पंक्ति पर लागू होता है। ^[19] एकरमैन फ़ंक्शन का व्युत्क्रम आदिम पुनरावर्ती है।^[20]

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

एकरमैन फ़ंक्शन, अत्यधिक गहरी रिकर्सन के संदर्भ में इसकी परिभाषा के कारण, रिकर्सन को अनुकूलित करने के लिए संकलक की क्षमता के बेंचमार्क के रूप में उपयोग किया जा सकता है। इस तरह से एकरमैन के कार्य का पहला प्रकाशित उपयोग 1970 में ड्रैगोस वैदा द्वारा किया गया था।^[21] और, लगभग एक साथ, 1971 में, येंगवे सुंदब्लाड द्वारा।^[13] 1975 और 1982 के बीच लिखे गए पत्रों की एक त्रयी में ब्रायन विचमैन (वेटस्टोन (बेंचमार्क) के सह-लेखक) द्वारा सुंदरब्लैड का मौलिक पेपर लिया गया था।^[22]^[23]^[24]

यह भी देखें

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

↑ with parameter order reversed
↑ 'curried'
↑ In each step the underlined redex is rewritten.
↑ ^4.0 ^4.1 here: leftmost-innermost strategy!
↑ ^5.0 ^5.1 ^5.2 ^5.3 For better readability
S(0) is notated as 1,
S(S(0)) is notated as 2,
S(S(S(0))) is notated as 3,
etc...
↑ The maximum depth of recursion refers to the number of levels of activation of a procedure which exist during the deepest call of the procedure. Cornelius & Kirby (1975)
↑ LOOP n+1 TIMES DO F

संदर्भ

↑ Monin & Hinchey 2003, p. 61.
↑ ^2.0 ^2.1 Ackermann 1928.
↑ "ए (4,2) का दशमलव विस्तार". kosara.net. August 27, 2000. Archived from the original on January 20, 2010.
↑ Calude, Marcus & Tevy 1979.
↑ Hilbert 1926, p. 185.
↑ van Heijenoort 1977.
↑ Péter 1935.
↑ Robinson 1948.
↑ Ritchie 1965, p. 1028.
↑ ^10.0 ^10.1 ^10.2 Buck 1963.
↑ Meeussen & Zantema 1992, p. 6.
↑ Munafo 1999a.
↑ ^13.0 ^13.1 Sundblad 1971.
↑ Porto & Matos 1980.
↑ Grossman & Zeitman 1988.
↑ Paulson 2021.
↑ Cohen 1987, p. 56, Proposition 3.16 (see in proof).
↑ Woo, Chi (2009-12-17). "एकरमैन फ़ंक्शन प्रिमिटिव रिकर्सिव | Planetmath.org नहीं है". planetmath.org (in English). Archived from the original on 2013-05-09.
↑ Pettie 2002.
↑ Matos 2014.
↑ Vaida 1970.
↑ Wichmann 1976.
↑ Wichmann 1977.
↑ Wichmann 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.

[letop3-10] with parameter order reversed

[letop4-16] 'curried'

[letop5-19] In each step the underlined redex is rewritten.

[letop2-20] 4.0 ^4.1 here: leftmost-innermost strategy!

[letop1-21] 5.0 ^5.1 ^5.2 ^5.3 For better readability
S(0) is notated as 1,
S(S(0)) is notated as 2,
S(S(S(0))) is notated as 3,
etc...

[letop6-23] The maximum depth of recursion refers to the number of levels of activation of a procedure which exist during the deepest call of the procedure. Cornelius & Kirby (1975)

[letop7-24] LOOP n+1 TIMES DO F

[FOOTNOTEMoninHinchey200361-1] Monin & Hinchey 2003, p. 61.

[FOOTNOTEAckermann1928-2] 2.0 ^2.1 Ackermann 1928.

[3] "ए (4,2) का दशमलव विस्तार". kosara.net. August 27, 2000. Archived from the original on January 20, 2010.

[FOOTNOTECaludeMarcusTevy1979-4] Calude, Marcus & Tevy 1979.

[FOOTNOTEHilbert1926185-5] Hilbert 1926, p. 185.

[FOOTNOTEvan_Heijenoort1977-6] van Heijenoort 1977.

[FOOTNOTEPéter1935-7] Péter 1935.

[FOOTNOTERobinson1948-8] Robinson 1948.

[FOOTNOTERitchie19651028-9] Ritchie 1965, p. 1028.

[FOOTNOTEBuck1963-11] 10.0 ^10.1 ^10.2 Buck 1963.

[FOOTNOTEMeeussenZantema19926-12] Meeussen & Zantema 1992, p. 6.

[FOOTNOTEMunafo1999a-13] Munafo 1999a.

[FOOTNOTESundblad1971-14] 13.0 ^13.1 Sundblad 1971.

[FOOTNOTEPortoMatos1980-15] Porto & Matos 1980.

[FOOTNOTEGrossmanZeitman1988-17] Grossman & Zeitman 1988.

[FOOTNOTEPaulson2021-18] Paulson 2021.

[FOOTNOTECohen198756Proposition_3.16_(see_in_proof)-22] Cohen 1987, p. 56, Proposition 3.16 (see in proof).

[25] Woo, Chi (2009-12-17). "एकरमैन फ़ंक्शन प्रिमिटिव रिकर्सिव | Planetmath.org नहीं है". planetmath.org (in English). Archived from the original on 2013-05-09.

[FOOTNOTEPettie2002-26] Pettie 2002.

[FOOTNOTEMatos2014-27] Matos 2014.

[FOOTNOTEVaida1970-28] Vaida 1970.

[FOOTNOTEWichmann1976-29] Wichmann 1976.

[FOOTNOTEWichmann1977-30] Wichmann 1977.

[FOOTNOTEWichmann1982-31] Wichmann 1982.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[n 1]

[10]

[11]

[12]

[13]

[14]

[n 2]

[15]

[16]

[n 3]

[n 4]

[n 5]

[17]

[n 6]

[n 7]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

v t e हाइपरऑपरेशन
प्राथमिक	उत्तराधिकारी (0) इसके अलावा (1) गुणा (2) घातांक (3) टेट्रेशन (4) पेंटेशन (5)
उलटा बाएं तर्क के लिए	पूर्ववर्ती (0) घटाव (1) डिवीजन (2) रूट निष्कर्षण (3) सुपर-रूट (4)
सही तर्क के लिए उलटा	पूर्ववर्ती (0) घटाव (1) डिवीजन (2) लॉगरिदम (3) सुपर-लॉगरिथम (4)
संबंधित आलेख	एकरमैन फ़ंक्शन कॉनवे जंजीर तीर अंकन Grzegorczyk पदानुक्रम नुथ अप-एरो नोटेशन Steinhaus -moser अंकन

Anonymous

Search

एकरमैन फलन

Namespaces

More

Page actions

Contents

इतिहास

परिभाषा

संगणना

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

बड़ी संख्या

मूल्यों की तालिका

गुण

सामान्य टिप्पणी

उलटा

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

यह भी देखें

टिप्पणियाँ

संदर्भ

ग्रन्थसूची

इस पेज में लापता आंतरिक लिंक की सूची

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

एकरमैन फलन

इतिहास

परिभाषा

संगणना

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

बड़ी संख्या

मूल्यों की तालिका

गुण

सामान्य टिप्पणी

उलटा

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

यह भी देखें

टिप्पणियाँ

संदर्भ

ग्रन्थसूची

इस पेज में लापता आंतरिक लिंक की सूची

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories