एकरमैन फलन: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Quickly-growing function}} {{About|the mathematical function||Ackermann (disambiguation)}} {{Use shortened footnotes|date=November 2022}} कम्प्...")
 
No edit summary
 
(33 intermediate revisions by 5 users not shown)
Line 1: Line 1:
{{Short description|Quickly-growing function}}
{{Short description|Quickly-growing function}}
{{About|the mathematical function||Ackermann (disambiguation)}}
{{About|गणितीय कार्य||एकरमैन (बहुविकल्पी)}}
 
{{Use shortened footnotes|date=November 2022}}
{{Use shortened footnotes|date=November 2022}}
कम्प्यूटेबिलिटी सिद्धांत में, [[विल्हेम एकरमैन]] के नाम पर एकरमैन फ़ंक्शन, सबसे सरल में से एक है{{sfn|Monin|Hinchey|2003|p=61}} और कुल फ़ंक्शन [[गणना योग्य समारोह]] के सबसे पहले खोजे गए उदाहरण जो आदिम पुनरावर्ती फ़ंक्शन नहीं हैं। सभी [[आदिम पुनरावर्ती कार्य]] कुल और संगणनीय हैं, लेकिन एकरमैन फ़ंक्शन यह दर्शाता है कि सभी कुल संगणनीय कार्य आदिम पुनरावर्ती नहीं हैं। एकरमैन के प्रकाशन के बाद{{sfn|Ackermann|1928}} उनके कार्य के (जिसमें तीन गैर-ऋणात्मक पूर्णांक तर्क थे), कई लेखकों ने इसे विभिन्न उद्देश्यों के अनुरूप संशोधित किया, ताकि आज एकरमैन फ़ंक्शन मूल फ़ंक्शन के कई रूपों में से किसी को भी संदर्भित कर सके। एक सामान्य संस्करण, दो-तर्क एकरमैन-पीटर फ़ंक्शन को गैर-नकारात्मक पूर्णांक ''m'' और ''n'' के लिए निम्नानुसार परिभाषित किया गया है:
 
संगणनीयता सिद्धांत में, [[विल्हेम एकरमैन]] के नाम पर एकरमैन फलन, जो सबसे सरल फलन में से एक है{{sfn|Monin|Hinchey|2003|p=61}} और सबसे पहले खोजे गए पूर्ण संगणनीय फलन का उदाहरण है जो कि मूल पुनरावर्ती फलन नहीं हैं। सभी [[आदिम पुनरावर्ती कार्य|मूल पुनरावर्ती फलन]] पूर्ण और संगणनीय हैं, लेकिन एकरमैन फलन यह दर्शाता है कि सभी पूर्ण संगणनीय फलन मूल फलन की पुनरावर्ती नहीं हैं। एकरमैन के प्रकाशन के बाद{{sfn|Ackermann|1928}} उनके फलन के (जिसमें तीन ऋणोतर पूर्णांक प्राचर थे), कई लेखकों ने इसे विभिन्न उद्देश्यों के अनुरूप संशोधित किया, ताकि एकरमैन फलन मूल फलन के कई रूपों में से किसी को भी संदर्भित कर सके। एक सामान्य संस्करण, दो-प्राचर एकरमैन-पीटर फलन को ऋणोतर पूर्णांक ''m'' और ''n'' के लिए निम्नानुसार परिभाषित किया गया है:


:<math>  
:<math>  
Line 11: Line 13:
\end{array}
\end{array}
</math>
</math>
छोटे इनपुट के लिए भी इसका मूल्य तेजी से बढ़ता है। उदाहरण के लिए, {{nowrap|''A''(4, 2)}} 19,729 दशमलव अंकों का पूर्णांक है<ref>{{cite web |title=ए (4,2) का दशमलव विस्तार|archive-url= https://web.archive.org/web/20100120134707/http://kosara.net/thoughts/ackermann42.html |date=August 27, 2000| url= http://www.kosara.net/thoughts/ackermann42.html|archive-date=January 20, 2010|website=kosara.net }}</ref> (2 के बराबर<sup>65536</sup>−3, या 2<sup>2<sup>2<sup>2<sup>2</sup></sup></sup></sup>−3).
छोटे आगम के लिए भी इसका मान तेजी से बढ़ता है। उदाहरण के लिए, {{nowrap|''A''(4, 2)}} 19,729 दशमलव अंकों का पूर्णांक है<ref>{{cite web |title=ए (4,2) का दशमलव विस्तार|archive-url= https://web.archive.org/web/20100120134707/http://kosara.net/thoughts/ackermann42.html |date=August 27, 2000| url= http://www.kosara.net/thoughts/ackermann42.html|archive-date=January 20, 2010|website=kosara.net }}</ref> ( 2<sup>65536</sup>−3 के बराबर, अथवा  2<sup>2<sup>2<sup>2<sup>2</sup></sup></sup></sup>−3).


== इतिहास ==
==इतिहास==
1920 के दशक के अंत में, गणितज्ञ [[गेब्रियल सूडान]] और विल्हेम एकरमैन, [[डेविड हिल्बर्ट]] के छात्र, संगणना की नींव का अध्ययन कर रहे थे। सूडान और एकरमैन दोनों को श्रेय दिया जाता है{{sfn|Calude|Marcus|Tevy|1979}} टोटल फंक्शन कंप्यूटेबल फंक्शन्स की खोज के साथ (जिसे कुछ संदर्भों में केवल रिकर्सिव कहा जाता है) जो प्रिमिटिव रिकर्सिव फंक्शन नहीं हैं। सूडान ने कम प्रसिद्ध सूडान कार्य प्रकाशित किया, फिर कुछ ही समय बाद और स्वतंत्र रूप से, 1928 में, एकरमैन ने अपना कार्य प्रकाशित किया <math>\varphi</math> (ग्रीक अक्षर [[फ़ाई]])एकरमैन का तीन-तर्क कार्य, <math>\varphi(m, n, p)</math>, के लिए परिभाषित किया गया है <math>p=0,1,2</math>, यह जोड़, [[गुणा]] और [[घातांक]] के बुनियादी संचालन को पुन: पेश करता है
1920 के दशक के अंत में, गणितज्ञ [[गेब्रियल सूडान]] और विल्हेम एकरमैन, [[डेविड हिल्बर्ट]] के छात्र, संगणना की नींव का अध्ययन कर रहे थे। सूडान और एकरमैन दोनों को पूर्ण संगणनीय फलन की खोज के लिए श्रेय दिया जाता है{{sfn|Calude|Marcus|Tevy|1979}} (जिसे कुछ संदर्भों में केवल "पुनरावर्ती" कहा जाता है) जो मूल पुनरावर्ती फलन नहीं हैं। सूडान ने कम प्रसिद्ध सूडान फलन प्रकाशित किया, फिर कुछ ही समय बाद और स्वतंत्र रूप से, 1928 में, एकरमैन ने अपना फलन  <math>\varphi</math> (ग्रीक अक्षर [[फ़ाई]]) प्रकाशित किया। एकरमैन का तीन-प्राचर फलन, <math>\varphi(m, n, p)</math>, को इस तरह से परिभाषित किया गया है कि यह जैसे  <math>p=0,1,2</math>, के लिए और यह योग, [[गुणा|गुणन]] और [[घातांक]] के बुनियादी परिचालनों का पुनरावृत्त करता है।


:<math>\begin{align}
:<math>\begin{align}
Line 21: Line 23:
\varphi(m, n, 2) &= m^n  
\varphi(m, n, 2) &= m^n  
\end{align}</math>
\end{align}</math>
और p > 2 के लिए यह इन बुनियादी संचालनों को एक तरह से विस्तारित करता है जिसकी तुलना [[हाइपरऑपरेशन]] से की जा सकती है:
और P > 2 के लिए यह इस तरह के बुनियादी परिचालनों को बढ़ाता है जिसकी तुलना [[हाइपरऑपरेशन|अतिसंचालन]] से की जा सकती है:


:<math>\begin{align}
:<math>\begin{align}
Line 27: Line 29:
\varphi(m, n, p) &\gtrapprox m[p+1](n+1) && \text{for } p > 3
\varphi(m, n, p) &\gtrapprox m[p+1](n+1) && \text{for } p > 3
\end{align}</math>
\end{align}</math>
(कुल-गणना योग्य-लेकिन-नहीं-आदिम-पुनरावर्ती कार्य के रूप में इसकी ऐतिहासिक भूमिका के अलावा, एकरमैन के मूल कार्य को घातांक से परे बुनियादी अंकगणितीय संचालन का विस्तार करने के लिए देखा जाता है, हालांकि एकरमैन के फ़ंक्शन के रूपांतरों के समान नहीं है जो विशेष रूप से डिज़ाइन किए गए हैं। वह उद्देश्य - जैसे रूबेन गुडस्टीन|गुडस्टीन का हाइपरऑपरेशन अनुक्रम।)
( इसकी ऐतिहासिक भूमिका के अलावा यह कुल-गणना योग्य-लेकिन-मूल-पुनरावर्ती फलन के रूप में नहीं, एकरमैन के मूल फलन को घातांक से परे बुनियादी अंकगणितीय संचालन का विस्तार करने के लिए देखा जाता है, हालांकि एकरमैन फलन के रूपांतरों के समान नहीं है जो विशेष रूप से डिज़ाइन किए गए हैं। जैसे कि - रूबेन गुडस्टीन का अतिसंचालन अनुक्रम।)
 
डेविड हिल्बर्ट ने परिकल्पना की कि एकरमैन फलन अनंत पर,{{sfn|Hilbert|1926|p=185}} मूल पुनरावर्ती नहीं था, लेकिन यह एकरमैन, हिल्बर्ट के निजी सचिव और पूर्व छात्र थे, जिन्होंने वास्तव में अपने कागज में वास्तविक संख्या के निर्माण पर परिकल्पना को सिद्ध किया था।{{sfn|Ackermann|1928}}{{sfn|van Heijenoort|1977}}
 
पीटर रोजसा{{sfn|Péter|1935}} और [[राफेल रॉबिन्सन]]{{sfn|Robinson|1948}}  ने बाद में एकरमैन फलन का एक दो-चर संस्करण को विकसित किया जो बाद में लगभग सभी लेखकों द्वारा पसंद किया गया।


अनंत पर में,{{sfn|Hilbert|1926|p=185}} डेविड हिल्बर्ट ने परिकल्पना की कि एकरमैन फ़ंक्शन आदिम पुनरावर्ती नहीं था, लेकिन यह एकरमैन, हिल्बर्ट के निजी सचिव और पूर्व छात्र थे, जिन्होंने वास्तव में अपने पेपर ऑन हिल्बर्ट्स कंस्ट्रक्शन ऑफ़ द रियल नंबर्स में परिकल्पना को साबित किया था।{{sfn|Ackermann|1928}}{{sfn|van Heijenoort|1977}}
सामान्यीकृत अतिसंचालन, उदाहरण - <math>G(m, a, b) = a[m]b</math>, एकरमैन फलन का भी एक संस्करण है।{{sfn|Ritchie|1965|p=1028}}
पीटर रोजसा{{sfn|Péter|1935}} और [[राफेल रॉबिन्सन]]{{sfn|Robinson|1948}} बाद में एकरमैन फ़ंक्शन का एक दो-चर संस्करण विकसित किया जो लगभग सभी लेखकों द्वारा पसंद किया गया।


सामान्यीकृत हाइपरऑपरेशन, उदा। <math>G(m, a, b) = a[m]b</math>, एकरमैन फ़ंक्शन का भी एक संस्करण है।{{sfn|Ritchie|1965|p=1028}}
1963 में आर.सी. बक अतिसंचालन सीक्वेंस पर एक सहज ज्ञान युक्त दो-चर <ref name="letop3" group="n">with parameter order reversed</ref>वेरिएंट <math>\operatorname{F}</math> पर आधारित है:{{sfn|Buck|1963}}{{sfn|Meeussen|Zantema|1992|p=6}}  
1963 में रॉबर्ट क्रेटन बक|आर.सी. बक एक सहज ज्ञान युक्त दो-चर आधारित है <ref group="n" name="letop3">with parameter order reversed</ref> प्रकार <math>\operatorname{F}</math> हाइपरऑपरेशन पर:{{sfn|Buck|1963}}{{sfn|Meeussen|Zantema|1992|p=6}}
:<math>\operatorname{F}(m,n) = 2[m]n.</math>
:<math>\operatorname{F}(m,n) = 2[m]n.</math>
अधिकांश अन्य संस्करणों की तुलना में बक के कार्य में कोई अनावश्यक ऑफ़सेट नहीं है:
अधिकांश अन्य संस्करणों की तुलना में बक के फलन में कोई अनावश्यक ऑफ़सेट नहीं है:


:<math>\begin{align}
:<math>\begin{align}
Line 45: Line 49:
  &\quad\vdots
  &\quad\vdots
\end{align}</math>
\end{align}</math>
एकरमैन फ़ंक्शन के कई अन्य संस्करणों की जांच की गई है।{{sfn|Munafo|1999a}}
एकरमैन फलन के कई अन्य संस्करणों का अन्वेषण भी किया गया है।{{sfn|Munafo|1999a}}
 
==परिभाषा==
 
======परिभाषा: एम-सरणी फलन के रूप में ======
== परिभाषा ==
एकरमैन का मूल तीन-प्राचर फलन <math>\varphi(m, n, p)</math> ऋणोतर पूर्णांकों <math>m,n,</math> तथा <math>p</math> के लिए निम्नानुसार पुनरावर्तन परिभाषित किया गया है :
 
=== परिभाषा: एम-एरी फ़ंक्शन === के रूप में
एकरमैन का मूल तीन-तर्क कार्य <math>\varphi(m, n, p)</math> गैर-नकारात्मक पूर्णांकों के लिए निम्नानुसार पुनरावर्तन परिभाषित किया गया है <math>m,n,</math> तथा <math>p</math>:


:<math>\begin{align}
:<math>\begin{align}
Line 60: Line 61:
\varphi(m, n, p) &= \varphi(m, \varphi(m, n-1, p), p - 1) && \text{for } n, p > 0
\varphi(m, n, p) &= \varphi(m, \varphi(m, n-1, p), p - 1) && \text{for } n, p > 0
\end{align}</math>
\end{align}</math>
विभिन्न दो-तर्क संस्करणों में से, पेटर और रॉबिन्सन द्वारा विकसित एक (जिसे अधिकांश लेखकों द्वारा एकरमैन फ़ंक्शन कहा जाता है) को गैर-नकारात्मक पूर्णांकों के लिए परिभाषित किया गया है <math>m</math> तथा <math>n</math> निम्नलिखित नुसार:
विभिन्न दो-प्राचर संस्करणों में से, पेटर और रॉबिन्सन द्वारा विकसित एक (जिसे अधिकांश लेखकों द्वारा एकरमैन फलन कहा जाता है) को ऋणोतर पूर्णांकों <math>m</math> तथा <math>n</math> के लिए निम्नलिखित अनुसार परिभाषित किया गया है :


:<math>  
:<math>  
Line 69: Line 70:
\end{array}
\end{array}
</math>
</math>
हाइपरऑपरेशन के संबंध में एकरमेन फ़ंक्शन भी व्यक्त किया गया है:{{sfn|Sundblad|1971}}{{sfn|Porto|Matos|1980}}
एकरमेन फलन को अतिसंचालन अनुक्रम के संबंध में भी व्यक्त किया गया है:{{sfn|Sundblad|1971}}{{sfn|Porto|Matos|1980}}
:<math>A(m,n) = \begin{cases}
:<math>A(m,n) = \begin{cases}
  n+1 & m=0 \\
  n+1 & m=0 \\
  2[m](n+3)-3 & m>0 \\
  2[m](n+3)-3 & m>0 \\
\end{cases}</math>
\end{cases}</math>
: या, नुथ के अप-एरो नोटेशन में लिखा गया है (पूर्णांक सूचकांकों तक विस्तारित <math>\geq -2</math>):
:या, नुथ के उच्च-तीर संकेतन में लिखा गया है (पूर्णांक सूचकांक में बढ़ाया गया <math>\geq -2</math>):
:::<math> = \begin{cases}
:::<math> = \begin{cases}
  n+1 & m=0 \\
  n+1 & m=0 \\
  2\uparrow^{m-2} (n+3) - 3 & m>0 \\
  2\uparrow^{m-2} (n+3) - 3 & m>0 \\
  \end{cases}</math>
  \end{cases}</math>
:या, समतुल्य रूप से, बक के फलन F के संदर्भ में:{{sfn|Buck|1963}} :::<math> = \begin{cases}
:या, समतुल्य रूप से, बक के फलन F के संदर्भ में:{{sfn|Buck|1963}}
:<math> = \begin{cases}
  n+1 & m=0 \\
  n+1 & m=0 \\
  F(m,n+3) - 3 & m>0 \\
  F(m,n+3) - 3 & m>0 \\
\end{cases}</math>
\end{cases}</math>


 
=====परिभाषा: पुनरावृत्त 1-सरणी फलन के रूप में परिभाषित करना=====
=== परिभाषा: पुनरावृत्त 1-एरी फ़ंक्शन === के रूप में
<math>f^{n}</math> के n-वें पुनरावृति के रूप में <math>f</math>:
परिभाषित करना <math>f^{n}</math> के n-वें पुनरावृति के रूप में <math>f</math>:
:<math>\begin{array}{rll}
:<math>\begin{array}{rll}
f^{0}(x) & = & x \\
f^{0}(x) & = & x \\
f^{n+1}(x) & = & f(f^{n}(x))\,\,\,\, \{\textrm{for} \,\, n \geq 1\}
f^{n+1}(x) & = & f(f^{n}(x))\,\,\,\, \{\textrm{for} \,\, n \geq 1\}
\end{array}</math>
\end{array}</math>
पुनरावृत्त फलन एक निश्चित संख्या में स्वयं के साथ एक फलन बनाने की प्रक्रिया है। फ़ंक्शन रचना एक साहचर्य ऑपरेशन है, इसलिए <math>f(f^{n}(x)) = f^{n}(f(x))</math>.
पुनरावृत्त फलन एक निश्चित संख्या में स्वयं के साथ एक फलन बनाने की प्रक्रिया है। फलन रचना एक साहचर्य संक्रिया है, इसलिए <math>f(f^{n}(x)) = f^{n}(f(x))</math>.


एकरमैन फ़ंक्शन को यूनरी फ़ंक्शंस के अनुक्रम के रूप में समझना, कोई सेट कर सकता है <math>\operatorname{A}_{m}(n) = \operatorname{A}(m,n)</math>.
एकरमैन फलन को एकल फलन के अनुक्रम के रूप में समझा जा सकता है ,यदि हम यह स्थापित कर सके कि  <math>\operatorname{A}_{m}(n) = \operatorname{A}(m,n)</math>.


समारोह तब एक अनुक्रम बन जाता है <math>\operatorname{A}_0, \operatorname{A}_1, \operatorname{A}_2, ...</math> यूनरी का<ref group="n" name="letop4">'[[Currying|curried]]'</ref> फ़ंक्शंस, इटरेटेड फ़ंक्शन से परिभाषित:
तब फलन एक एकल <ref name="letop4" group="n">'[[Currying|curried]]'</ref> फलन का अनुक्रम <math>\operatorname{A}_0, \operatorname{A}_1, \operatorname{A}_2, ...</math> ,होगा  जिसे हम पुनरावृत्त फलन से पारिभाषित कर सकते है :
:<math>  
:<math>  
\begin{array}{lcl}
\begin{array}{lcl}
Line 104: Line 105:




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


=== टीआरएस, 2-एरी फ़ंक्शन === पर आधारित है
=====टीआरएस, 2-सरणी फलन पर आधारित है=====
<u>2-ary</u> एकरमैन फ़ंक्शन की परिभाषा स्पष्ट कमी नियमों की ओर ले जाती है {{sfn|Grossman|Zeitman|1988}}{{sfn|Paulson|2021}}
<u>2-सरणी</u> एकरमैन फलन की परिभाषा स्पष्ट कटौती नियम की ओर ले जाती है {{sfn|Grossman|Zeitman|1988}}{{sfn|Paulson|2021}}
:<math>  
:<math>  
\begin{array}{lll}
\begin{array}{lll}
Line 118: Line 119:
उदाहरण
उदाहरण


गणना करना <math>A(1,2) \rightarrow_{*} 4</math>
गणना करने पर <math>A(1,2) \rightarrow_{*} 4</math>
घटाव क्रम है <ref group="n" name="letop5">In each ''step'' the underlined ''redex'' is rewritten.</ref>
 
कमी अनुक्रम है <ref group="n" name="letop5">In each ''step'' the underlined ''redex'' is rewritten.</ref>


{|
{|
|align="left"|[[Reduction strategy#Term rewriting|Leftmost-outermost (one-step) strategy]]:{{space|12}}
| align="left" |[[Reduction strategy#Term rewriting|बाएँ सबसे बाहरी (एक कदम) नीतिबद्ध]]:{{space|12}}
|align="left"|[[Reduction strategy#Term rewriting|Leftmost-innermost (one-step) strategy]]:
| align="left" |[[Reduction strategy#Term rewriting|बांयी ओर-अंतरतम (एक-चरणीय) नीतिबद्ध]]:
|-
|-
|<math>\underline{{A(S(0),S(S(0)))}}</math>
|<math>\underline{{A(S(0),S(S(0)))}}</math>
Line 159: Line 161:
योजनाबद्ध रूप से, से शुरू <math>\langle m,n \rangle</math>:
योजनाबद्ध रूप से, से शुरू <math>\langle m,n \rangle</math>:


  जबकि ढेर की लंबाई <> 1
  '''WHILE''' stackLength <> 1
  {
  {
     पीओपी 2 तत्व;
     '''POP''' 2 elements;
     PUSH 1 या 2 या 3 तत्व, नियमों को लागू करते हुए r1, r2, r3
     '''PUSH''' 1 or 2 or 3 elements, applying the rules r1, r2, r3
  }
  }


[[स्यूडोकोड]] प्रकाशित हो चुकी है। {{harvtxt|Grossman|Zeitman|1988}}.
[[स्यूडोकोड]] प्रकाशित हो चुकी है। {{harvtxt|ग्रॉसमैन|जेटमन|1988}}.


उदाहरण के लिए, इनपुट पर <math>\langle 2,1 \rangle</math>,
उदाहरण के लिए, आगम पर <math>\langle 2,1 \rangle</math>,
{|
{|
|align="left"|the stack configurations{{space|4}}
| align="left" |स्टैक का विन्यास{{space|4}}
|align="left"|reflect the reduction<ref group="n" name="letop1">For better readability<br/>S(0) is notated as 1,<br />S(S(0)) is notated as 2,<br />S(S(S(0))) is notated as 3,<br/>etc...</ref>
| align="left" |कमी को दर्शाना <ref group="n" name="letop1">For better readability<br />S(0) is notated as 1,<br />S(S(0)) is notated as 2,<br />S(S(S(0))) is notated as 3,<br />etc...</ref>
|-
|-
|<math>\underline{2,1}</math>  
|<math>\underline{2,1}</math>
|<math>\underline{A(2,1)}</math>
|<math>\underline{A(2,1)}</math>
|-
|-
|{{space|4}}<math>\rightarrow 1,\underline{2,0}</math>
|{{space|4}}<math>\rightarrow 1,\underline{2,0}</math>
|{{space|4}}<math>\rightarrow_{r1} A(1,\underline{A(2,0)})</math>
|{{space|4}}<math>\rightarrow_{r1} A(1,\underline{A(2,0)})</math>
|-
|-
|{{space|4}}<math>\rightarrow 1,\underline{1,1}</math>
|{{space|4}}<math>\rightarrow 1,\underline{1,1}</math>
|{{space|4}}<math>\rightarrow_{r2} A(1,\underline{A(1,1)})</math>
|{{space|4}}<math>\rightarrow_{r2} A(1,\underline{A(1,1)})</math>
|-
|-
|{{space|4}}<math>\rightarrow 1,0,\underline{1,0}</math>
|{{space|4}}<math>\rightarrow 1,0,\underline{1,0}</math>
|{{space|4}}<math>\rightarrow_{r3} A(1,A(0,\underline{A(1,0)}))</math>
|{{space|4}}<math>\rightarrow_{r3} A(1,A(0,\underline{A(1,0)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow 1,0,\underline{0,1}</math>
|{{space|4}}<math>\rightarrow 1,0,\underline{0,1}</math>
|{{space|4}}<math>\rightarrow_{r2} A(1,A(0,\underline{A(0,1)}))</math>
|{{space|4}}<math>\rightarrow_{r2} A(1,A(0,\underline{A(0,1)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow 1,\underline{0,2}</math>
|{{space|4}}<math>\rightarrow 1,\underline{0,2}</math>
|{{space|4}}<math>\rightarrow_{r1} A(1,\underline{A(0,2)})</math>
|{{space|4}}<math>\rightarrow_{r1} A(1,\underline{A(0,2)})</math>
|-
|-
|{{space|4}}<math>\rightarrow \underline{1,3}</math>
|{{space|4}}<math>\rightarrow \underline{1,3}</math>
|{{space|4}}<math>\rightarrow_{r1} \underline{A(1,3)}</math>
|{{space|4}}<math>\rightarrow_{r1} \underline{A(1,3)}</math>
|-
|-
|{{space|4}}<math>\rightarrow 0,\underline{1,2}</math>
|{{space|4}}<math>\rightarrow 0,\underline{1,2}</math>
|{{space|4}}<math>\rightarrow_{r3} A(0,\underline{A(1,2)})</math>
|{{space|4}}<math>\rightarrow_{r3} A(0,\underline{A(1,2)})</math>
|-
|-
|{{space|4}}<math>\rightarrow 0,0,\underline{1,1}</math>
|{{space|4}}<math>\rightarrow 0,0,\underline{1,1}</math>
|{{space|4}}<math>\rightarrow_{r3} A(0,A(0,\underline{A(1,1)}))</math>
|{{space|4}}<math>\rightarrow_{r3} A(0,A(0,\underline{A(1,1)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow 0,0,0,\underline{1,0}</math>
|{{space|4}}<math>\rightarrow 0,0,0,\underline{1,0}</math>
|{{space|4}}<math>\rightarrow_{r3} A(0,A(0,A(0,\underline{A(1,0)})))</math>
|{{space|4}}<math>\rightarrow_{r3} A(0,A(0,A(0,\underline{A(1,0)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow 0,0,0,\underline{0,1}</math>
|{{space|4}}<math>\rightarrow 0,0,0,\underline{0,1}</math>
|{{space|4}}<math>\rightarrow_{r2} A(0,A(0,A(0,\underline{A(0,1)})))</math>
|{{space|4}}<math>\rightarrow_{r2} A(0,A(0,A(0,\underline{A(0,1)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow 0,0,\underline{0,2}</math>
|{{space|4}}<math>\rightarrow 0,0,\underline{0,2}</math>
|{{space|4}}<math>\rightarrow_{r1} A(0,A(0,\underline{A(0,2)}))</math>
|{{space|4}}<math>\rightarrow_{r1} A(0,A(0,\underline{A(0,2)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow 0,\underline{0,3}</math>
|{{space|4}}<math>\rightarrow 0,\underline{0,3}</math>
|{{space|4}}<math>\rightarrow_{r1} A(0,\underline{A(0,3)})</math>
|{{space|4}}<math>\rightarrow_{r1} A(0,\underline{A(0,3)})</math>
|-
|-
|{{space|4}}<math>\rightarrow \underline{0,4}</math>
|{{space|4}}<math>\rightarrow \underline{0,4}</math>
|{{space|4}}<math>\rightarrow_{r1} \underline{A(0,4)}</math>
|{{space|4}}<math>\rightarrow_{r1} \underline{A(0,4)}</math>
|-
|-
|{{space|4}}<math>\rightarrow 5</math>
|{{space|4}}<math>\rightarrow 5</math>
|{{space|4}}<math>\rightarrow_{r1} 5</math>
|{{space|4}}<math>\rightarrow_{r1} 5</math>
|}
|}
टिप्पणियां
टिप्पणियां  
*[[रोसेटा कोड]] पर 225 कंप्यूटर भाषाओं में सबसे वामपंथी-अंतरतम रणनीति लागू की गई है।
*[[रोसेटा कोड]] पर 225 कंप्यूटर भाषाओं में सबसे बांयी ओर-अंतरतम नीति लागू की गई है।
*सभी के लिए <math>m,n</math> की गणना <math>A(m,n)</math> से अधिक नहीं लेता है <math>(A(m,n) + 1)^m</math> कदम।{{sfn|Cohen|1987|p=56|loc=Proposition 3.16 (see in proof)}}
*सभी <math>m,n</math> की गणना के लिए <math>A(m,n)</math> फलन <math>(A(m,n) + 1)^m</math> कदम से अधिक नहीं लेता है{{sfn|Cohen|1987|p=56|loc=Proposition 3.16 (see in proof)}}
*{{harvtxt|Grossman|Zeitman|1988}} बताया कि की गणना में <math>\operatorname{A}(m,n)</math> ढेर की अधिकतम लंबाई है <math>\operatorname{A}(m,n)</math>, जब तक कि <math>m>0</math>.
*{{harvtxt|ग्रॉसमैन |जेटमन|1988}} बताया कि <math>\operatorname{A}(m,n)</math> स्टैक  की गणना में अधिकतम लंबाई <math>\operatorname{A}(m,n)</math>, है  जब कि <math>m>0</math>.
: उनका अपना एल्गोरिदम, स्वाभाविक रूप से पुनरावृत्त, गणना करता है <math>\operatorname{A}(m,n)</math> अंदर <math>\mathcal{O}(m \operatorname{A}(m,n))</math> समय और भीतर <math>\mathcal{O}(m)</math> अंतरिक्ष।
:उनका अपना कलन विधि, स्वाभाविक रूप से पुनरावृत्त, गणना करता है <math>\operatorname{A}(m,n)</math> अंदर <math>\mathcal{O}(m \operatorname{A}(m,n))</math> समय और भीतर <math>\mathcal{O}(m)</math> स्थान ।


=== टीआरएस, पुनरावृत्त 1-एरी फ़ंक्शन === पर आधारित है
===== टीआरएस, पुनरावृत्त 1-सरणी फलन पर आधारित है =====
पुनरावृत्त <u>1-ary</u> एकरमैन फ़ंक्शन की परिभाषा विभिन्न कमी नियमों की ओर ले जाती है
पुनरावृत्त <u>1-सरणी</u> एकरमैन फलन की परिभाषा विभिन्न कमी नियमों की ओर ले जाती है
:<math>  
:<math>  
\begin{array}{lll}
\begin{array}{lll}
Line 232: Line 234:
\end{array}
\end{array}
</math>
</math>
जैसा कि फ़ंक्शन रचना साहचर्य है, नियम r6 के बजाय परिभाषित किया जा सकता है
जैसा कि फलन रचना साहचर्य है, नियम r6 के बजाय परिभाषित किया जा सकता है
:<math>
:<math>
\begin{array}{lll}
\begin{array}{lll}
Line 238: Line 240:
\end{array}
\end{array}
</math>
</math>
पिछले खंड की तरह की गणना <math>\operatorname{A}^1_m(n)</math> ढेर के साथ लागू किया जा सकता है।
पिछले खंड की तरह की गणना <math>\operatorname{A}^1_m(n)</math> स्टैक के साथ लागू किया जा सकता है।
 
प्रारंभ में स्टैक में तीन तत्व होते हैं <math>\langle 1,m,n \rangle</math>.


प्रारंभ में ढेर में तीन तत्व होते हैं <math>\langle 1,m,n \rangle</math>.
फिर बार-बार तीन शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है<ref group="n" name="letop2" />:


फिर बार-बार तीन शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है<ref group="n" name="letop2"/>:<math>
<math>
\begin{array}{lllllllll}
\begin{array}{lllllllll}
\text{(r4)} & 1  &, 0  &, n & \rightarrow & (n+1) \\
\text{(r4)} & 1  &, 0  &, n & \rightarrow & (n+1) \\
Line 249: Line 253:
\end{array}
\end{array}
</math>
</math>
योजनाबद्ध रूप से, से शुरू <math>\langle 1, m,n \rangle</math>:
योजनाबद्ध रूप से, से शुरू <math>\langle 1, m,n \rangle</math>:
  जबकि ढेर की लंबाई <> 1
  '''WHILE''' stackLength <> 1
  {
  {
     पीओपी 3 तत्व;
     '''POP''' 3 elements;
     पुश 1 या 3 या 5 तत्व, नियमों को लागू करना r4, r5, r6;
     '''PUSH''' 1 or 3 or 5 elements, applying the rules r4, r5, r6;
  }
  }


उदाहरण
उदाहरण


इनपुट पर <math>\langle 1,2,1 \rangle</math> क्रमिक ढेर विन्यास हैं
आगम पर <math>\langle 1,2,1 \rangle</math> क्रमिक स्टैक विन्यास हैं  
:<math>\begin{align}
:<math>\begin{align}
& \underline{1,2,1}
& \underline{1,2,1}
Line 276: Line 281:
   \rightarrow_{r4} 5
   \rightarrow_{r4} 5
\end{align}</math>
\end{align}</math>
संगत समानताएं हैं
संगत समानताएं हैं
:<math>\begin{align}
:<math>\begin{align}
& A_2(1)
& A_2(1)
Line 316: Line 321:
   \rightarrow_{r4} 5
   \rightarrow_{r4} 5
\end{align}</math>
\end{align}</math>
संगत समानताएं हैं
संगत समानताएं हैं
:<math>\begin{align}
:<math>\begin{align}
& A_2(1)
& A_2(1)
Line 333: Line 338:
\end{align}</math>
\end{align}</math>
टिप्पणियां
टिप्पणियां
*किसी दिए गए इनपुट पर अब तक प्रस्तुत टीआरएस समान चरणों में अभिसरण करते हैं। वे समान कटौती नियमों का भी उपयोग करते हैं (इस तुलना में नियमों r1, r2, r3 को क्रमशः नियम r4, r5, r6/r7 के समान माना जाता है)। उदाहरण के लिए, की कमी <math>A(2,1)</math> 14 चरणों में अभिसरित होता है: 6 × r1, 3 × r2, 5 × r3। की कमी <math>A_2(1)</math> समान 14 चरणों में अभिसरित होता है: 6 × r4, 3 × r5, 5 × r6/r7। टीआरएस उस क्रम में भिन्न होते हैं जिसमें कटौती नियम लागू होते हैं।
*किसी दिए गए आगम पर अब तक प्रस्तुत टीआरएस ने अभी तक चरणों की एक ही संख्या में एकजुट किया है। वे समान कटौती नियमों का भी उपयोग करते हैं (इस तुलना में नियमों r1, r2, r3 को क्रमशः नियम r4, r5, r6/r7 के समान माना जाता है)। उदाहरण के लिए, एक  <math>A(2,1)</math> की कटौती 14 चरणों में अभिसरित होता है: 6 × r1, 3 × r2, 5 × r3। की कमी <math>A_2(1)</math> समान 14 चरणों में अभिसरित होता है: 6 × r4, 3 × r5, 5 × r6/r7। टीआरएस उस क्रम में भिन्न होते हैं जिसमें कमी के नियम लागू होते हैं।
*कब <math>A_{i}(n)</math> {r4, r5, r6} नियमों का पालन करते हुए गणना की जाती है, स्टैक की अधिकतम लंबाई नीचे रहती है <math>2 \times A(i,n)</math>. जब नियम r6 के स्थान पर कमी नियम r7 का उपयोग किया जाता है, तो स्टैक की अधिकतम लंबाई केवल होती है <math>2(i+2)</math>. ढेर की लंबाई रिकर्सन गहराई को दर्शाती है। नियमों के अनुसार कमी के रूप में {r4, r5, r7} में पुनरावर्तन की एक छोटी अधिकतम गहराई शामिल है,<ref group="n" name="letop6">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. {{harvtxt|Cornelius|Kirby|1975}}</ref> यह गणना उस संबंध में अधिक कुशल है।
* कब <math>A_{i}(n)</math> नियमों का पालन करते हुए {r4, r5, r6} गणना की जाती है, स्टैक की अधिकतम लंबाई <math>2 \times A(i,n)</math> के नीचे रहती है जब कमी नियम r6 के स्थान पर कमी नियम r7 का उपयोग किया जाता है, तो स्टैक की अधिकतम लंबाई केवल <math>2(i+2)</math> होती है। स्टैक की लंबाई पुनरावर्ती गहराई को दर्शाती है। नियमों के अनुसार कमी के रूप में {r4, r5, r7} में पुनरावर्तन की एक छोटी अधिकतम गहराई शामिल है,<ref group="n" name="letop6">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. {{harvtxt|Cornelius|Kirby|1975}}</ref> यह गणना उस संबंध में अधिक कुशल है।


=== टीआरएस, हाइपरऑपरेटरों पर आधारित ===
===टीआरएस, हाइपरऑपरेटरों पर आधारित===
जैसा {{harvtxt|Sundblad|1971}} - या {{harvtxt|Porto|Matos|1980}} - स्पष्ट रूप से दिखाया गया है, एकरमेन फ़ंक्शन हाइपरऑपरेशन अनुक्रम के संदर्भ में व्यक्त किया जा सकता है:
जैसा {{harvtxt|सुंदब्लाड |1971}} - या {{harvtxt|पोर्टो|माटोस |1980}} - स्पष्ट रूप से दिखाया गया है, एकरमेन फलन अतिसंचालन अनुक्रम के संदर्भ में व्यक्त किया जा सकता है:
:<math>A(m,n) = \begin{cases}
:<math>A(m,n) = \begin{cases}
  n+1 & m=0 \\
  n+1 & m=0 \\
  2[m](n+3) - 3 & m>0 \\
  2[m](n+3) - 3 & m>0 \\
\end{cases}</math>
\end{cases}</math>
या, बक के कार्य के संदर्भ में, पैरामीटर सूची से निरंतर 2 को हटाने के बाद
या, बक के फलन के संदर्भ में, पैरामीटर सूची से निरंतर 2 को हटाने के बाद
    
    
:::<math> = \begin{cases}
:::<math> = \begin{cases}
Line 348: Line 353:
  F(m,n+3) - 3 & m>0 \\
  F(m,n+3) - 3 & m>0 \\
\end{cases}</math>
\end{cases}</math>
बक का कार्य <math>\operatorname{F}(m,n) = 2[m]n</math>,{{sfn|Buck|1963}} एकरमैन फ़ंक्शन का एक भिन्न रूप, जिसकी गणना निम्न कमी नियमों के साथ की जा सकती है:
बक का फलन <math>\operatorname{F}(m,n) = 2[m]n</math>,{{sfn|Buck|1963}} एकरमैन फलन का एक भिन्न रूप, जिसकी गणना निम्न कमी नियमों के साथ की जा सकती है:
:<math>  
:<math>  
\begin{array}{lll}
\begin{array}{lll}
Line 365: Line 370:
\end{array}
\end{array}
</math>
</math>
एकरमैन फ़ंक्शन की गणना करने के लिए तीन कटौती नियमों को जोड़ना पर्याप्त है
एकरमैन फलन की गणना करने के लिए तीन कटौती नियमों को जोड़ना पर्याप्त है
:<math>  
:<math>  
\begin{array}{lll}
\begin{array}{lll}
Line 373: Line 378:
\end{array}
\end{array}
</math>
</math>
ये नियम बेस केस (0, एन), संरेखण (एन + 3) और फज (-3) का ख्याल रखते हैं।
ये नियम बेस केस A (0, n), संरेखण (n + 3) और फज (-3) का ख्याल रखते हैं।


उदाहरण
उदाहरण
Line 379: Line 384:
गणना करना <math>A(2,1) \rightarrow_{*} 5</math>
गणना करना <math>A(2,1) \rightarrow_{*} 5</math>
{|
{|
|align="left"|using reduction rule <math>\text{b7}</math>:<ref group="n" name="letop1"/>{{space|4}}
| align="left" |कमी नियम के उपयोग से  <math>\text{b7}</math>:<ref group="n" name="letop1" />{{space|4}}
|align="left"|using reduction rule <math>\text{b6}</math>:<ref group="n" name="letop1"/>
| align="left" |कमी नियम के उपयोग से  <math>\text{b6}</math>:<ref group="n" name="letop1" />
|-
|-
|<math>\underline{A(2,1)}</math>
|<math>\underline{A(2,1)}</math>
Line 391: Line 396:
|{{space|4}}<math>\rightarrow_{b5} P(F(4,1,\underline{F(1,2,0)}))</math>
|{{space|4}}<math>\rightarrow_{b5} P(F(4,1,\underline{F(1,2,0)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b3} P(\underline{F(4,1,0)})</math>
|{{space|4}}<math>\rightarrow_{b3} P(\underline{F(4,1,0)})</math>
|{{space|4}}<math>\rightarrow_{b3} P(\underline{F(4,1,0)})</math>
|{{space|4}}<math>\rightarrow_{b3} P(\underline{F(4,1,0)})</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(3,1,\underline{F(1,1,0)}))</math>
|{{space|4}}<math>\rightarrow_{b7} P(F(3,1,\underline{F(1,1,0)}))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,\underline{F(3,1,0)}))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,\underline{F(3,1,0)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b2} P(\underline{F(3,1,2)})</math>
|{{space|4}}<math>\rightarrow_{b2} P(\underline{F(3,1,2)})</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,1,\underline{F(2,1,0)})))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,1,\underline{F(2,1,0)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(2,1,\underline{F(1,1,2)}))</math>
|{{space|4}}<math>\rightarrow_{b7} P(F(2,1,\underline{F(1,1,2)}))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,1,F(1,1,\underline{F(1,1,0)}))))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,1,F(1,1,\underline{F(1,1,0)}))))</math>
|-
|-
Line 406: Line 411:
|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,F(1,1,\underline{F(1,1,2)})))</math>
|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,F(1,1,\underline{F(1,1,2)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b2} P(F(2,1,\underline{F(2,0,2)}))</math>
|{{space|4}}<math>\rightarrow_{b2} P(F(2,1,\underline{F(2,0,2)}))</math>
|{{space|4}}<math>\rightarrow_{b5} P(F(1,1,F(1,1,F(2,0,\underline{F(1,1,0)}))))</math>
|{{space|4}}<math>\rightarrow_{b5} P(F(1,1,F(1,1,F(2,0,\underline{F(1,1,0)}))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(2,1,F(1,0,\underline{F(1,0,2)})))</math>  
|{{space|4}}<math>\rightarrow_{b7} P(F(2,1,F(1,0,\underline{F(1,0,2)})))</math>
|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,F(1,1,\underline{F(2,0,2)})))</math>
|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,F(1,1,\underline{F(2,0,2)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(F(2,1,\underline{F(1,0,3)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(2,1,\underline{F(1,0,3)}))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,1,F(1,0,\underline{F(1,0,2)}))))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,1,F(1,0,\underline{F(1,0,2)}))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(2,1,4)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(2,1,4)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,F(1,1,\underline{F(1,0,3)})))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,F(1,1,\underline{F(1,0,3)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,\underline{F(1,1,4)}))</math>
|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,\underline{F(1,1,4)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(1,1,4)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(1,1,4)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b5} P(F(1,1,F(4,0,\underline{F(1,1,0)})))</math>  
|{{space|4}}<math>\rightarrow_{b5} P(F(1,1,F(4,0,\underline{F(1,1,0)})))</math>
|{{space|4}}<math>\rightarrow_{b5} P(F(1,1,F(4,0,\underline{F(1,1,0)})))</math>
|{{space|4}}<math>\rightarrow_{b5} P(F(1,1,F(4,0,\underline{F(1,1,0)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,\underline{F(4,0,2)}))</math>
|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,\underline{F(4,0,2)}))</math>
|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,\underline{F(4,0,2)}))</math>
|{{space|4}}<math>\rightarrow_{b2} P(F(1,1,\underline{F(4,0,2)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,F(3,0,\underline{F(1,0,2)})))</math>  
|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,F(3,0,\underline{F(1,0,2)})))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,0,\underline{F(3,0,2)})))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,0,\underline{F(3,0,2)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(3,0,3)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(3,0,3)}))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,0,F(1,0,\underline{F(2,0,2)}))))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,0,F(1,0,\underline{F(2,0,2)}))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,F(2,0,\underline{F(1,0,3)})))</math>  
|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,F(2,0,\underline{F(1,0,3)})))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,0,F(1,0,F(1,0,\underline{F(1,0,2)})))))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,1,F(1,0,F(1,0,F(1,0,\underline{F(1,0,2)})))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(2,0,4)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(2,0,4)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,F(1,0,F(1,0,\underline{F(1,0,3)}))))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,F(1,0,F(1,0,\underline{F(1,0,3)}))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,F(1,0,\underline{F(1,0,4)})))</math>  
|{{space|4}}<math>\rightarrow_{b7} P(F(1,1,F(1,0,\underline{F(1,0,4)})))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,F(1,0,\underline{F(1,0,4)})))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,F(1,0,\underline{F(1,0,4)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(1,0,5)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(1,0,5)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(1,0,5)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,1,\underline{F(1,0,5)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,1,6)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,1,6)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,1,6)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,1,6)})</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b5} P(F(6,0,\underline{F(1,1,0)}))</math>
|{{space|4}}<math>\rightarrow_{b5} P(F(6,0,\underline{F(1,1,0)}))</math>
|{{space|4}}<math>\rightarrow_{b5} P(F(6,0,\underline{F(1,1,0)}))</math>
|{{space|4}}<math>\rightarrow_{b5} P(F(6,0,\underline{F(1,1,0)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b2} P(\underline{F(6,0,2)})</math>
|{{space|4}}<math>\rightarrow_{b2} P(\underline{F(6,0,2)})</math>
|{{space|4}}<math>\rightarrow_{b2} P(\underline{F(6,0,2)})</math>
|{{space|4}}<math>\rightarrow_{b2} P(\underline{F(6,0,2)})</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(5,0,\underline{F(1,0,2)}))</math>
|{{space|4}}<math>\rightarrow_{b7} P(F(5,0,\underline{F(1,0,2)}))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,\underline{F(5,0,2)}))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,\underline{F(5,0,2)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(5,0,3)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(5,0,3)})</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,\underline{F(4,0,2)})))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,\underline{F(4,0,2)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(4,0,\underline{F(1,0,3)}))</math>
|{{space|4}}<math>\rightarrow_{b7} P(F(4,0,\underline{F(1,0,3)}))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,F(1,0,\underline{F(3,0,2)}))))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,F(1,0,\underline{F(3,0,2)}))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(4,0,4)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(4,0,4)})</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,F(1,0,F(1,0,\underline{F(2,0,2)})))))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,F(1,0,F(1,0,\underline{F(2,0,2)})))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(3,0,\underline{F(1,0,4)}))</math>
|{{space|4}}<math>\rightarrow_{b7} P(F(3,0,\underline{F(1,0,4)}))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,\underline{F(1,0,2)}))))))</math>
|{{space|4}}<math>\rightarrow_{b6} P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,\underline{F(1,0,2)}))))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(3,0,5)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(3,0,5)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,F(1,0,F(1,0,F(1,0,\underline{F(1,0,3)})))))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,F(1,0,F(1,0,F(1,0,\underline{F(1,0,3)})))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(2,0,\underline{F(1,0,5)}))</math>
|{{space|4}}<math>\rightarrow_{b7} P(F(2,0,\underline{F(1,0,5)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,F(1,0,F(1,0,\underline{F(1,0,4)}))))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,F(1,0,F(1,0,\underline{F(1,0,4)}))))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(2,0,6)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(2,0,6)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,F(1,0,\underline{F(1,0,5)})))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,F(1,0,\underline{F(1,0,5)})))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b7} P(F(1,0,\underline{F(1,0,6)}))</math>
|{{space|4}}<math>\rightarrow_{b7} P(F(1,0,\underline{F(1,0,6)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,\underline{F(1,0,6)}))</math>
|{{space|4}}<math>\rightarrow_{b1} P(F(1,0,\underline{F(1,0,6)}))</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,0,7)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,0,7)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,0,7)})</math>
|{{space|4}}<math>\rightarrow_{b1} P(\underline{F(1,0,7)})</math>
|-
|-
|{{space|4}}<math>\rightarrow_{b1} \underline{P(8)}</math>
|{{space|4}}<math>\rightarrow_{b1} \underline{P(8)}</math>
|{{space|4}}<math>\rightarrow_{b1} \underline{P(8)}</math>
|{{space|4}}<math>\rightarrow_{b1} \underline{P(8)}</math>
|-
|-
|{{space|4}}<math>\rightarrow_{r10} 5</math>
|{{space|4}}<math>\rightarrow_{r10} 5</math>
|{{space|4}}<math>\rightarrow_{r10} 5</math>
|{{space|4}}<math>\rightarrow_{r10} 5</math>
|}
|}
मिलान करने वाली समानताएं हैं
मिलान करने वाली समानताएं हैं  
* जब टीआरएस कटौती नियम के साथ <math>\text{b6}</math> लागू की गई है:
*जब टीआरएस कटौती नियम के साथ <math>\text{b6}</math> लागू की गई है:
:<math>\begin{align}
:<math>\begin{align}
& A(2,1) +3
& A(2,1) +3
Line 509: Line 514:
= 8
= 8
\end{align}</math>
\end{align}</math>
* जब टीआरएस कटौती नियम के साथ <math>\text{b7}</math> लागू की गई है:
*जब टीआरएस कटौती नियम के साथ <math>\text{b7}</math> लागू की गई है:
:<math>\begin{align}
:<math>\begin{align}
& A(2,1) +3
& A(2,1) +3
Line 528: Line 533:
\end{align}</math>
\end{align}</math>
टिप्पणियां
टिप्पणियां
* की गणना <math>\operatorname{A}_{i}(n)</math> नियमों के मुताबिक {बी 1 - बी 5, बी 6, आर 8 - आर 10} गहरा रिकर्सिव है। नेस्टेड की अधिकतम गहराई <math>F</math>एस है <math>A(i,n)+1</math>. अपराधी वह क्रम है जिसमें पुनरावृत्ति निष्पादित होती है: <math>F^{n+1}(x) = F(F^{n}(x))</math>. सबसे पहला <math>F</math> पूरे क्रम के सामने आने के बाद ही गायब हो जाता है।
*की गणना <math>\operatorname{A}_{i}(n)</math> नियमों के मुताबिक {b1 - b5, b6, r8 - r10} गहरा पुनरावर्ती है। नेस्टेड की अधिकतम गहराई <math>F</math> एस है <math>A(i,n)+1</math>. अपराधी वह क्रम है जिसमें पुनरावृत्ति निष्पादित होती है: <math>F^{n+1}(x) = F(F^{n}(x))</math>. सबसे पहला <math>F</math> पूरे क्रम के सामने आने के बाद ही गायब हो जाता है।
*नियमों के अनुसार गणना {b1 - b5, b7, r8 - r10} उस संबंध में अधिक कुशल है। पुनरावृत्ति <math>F^{n+1}(x) = F^{n}(F(x))</math> कोड के एक ब्लॉक पर बार-बार लूप को सिम्युलेट करता है।<ref group="n" name="letop7">'''LOOP''' n+1 '''TIMES DO''' F</ref> घोंसला बनाना तक सीमित है <math>(i+1)</math>, प्रति पुनरावृत्त कार्य के लिए एक पुनरावर्तन स्तर। {{harvtxt|Meyer|Ritchie|1967}} यह पत्राचार दिखाया।
*नियमों के अनुसार गणना {b1 - b5, b7, r8 - r10} उस संबंध में अधिक कुशल है। पुनरावृत्ति <math>F^{n+1}(x) = F^{n}(F(x))</math> कोड के एक ब्लॉक पर बार-बार लूप को सिम्युलेट करता है।<ref group="n" name="letop7">'''LOOP''' n+1 '''TIMES DO''' F</ref> घोंसला बनाना तक सीमित है <math>(i+1)</math>, प्रति पुनरावृत्त फलन के लिए एक पुनरावर्तन स्तर। {{harvtxt|मेयर|रिची|1967}} यह पत्राचार दिखाया।
* ये विचार केवल पुनरावर्तन गहराई से संबंधित हैं। पुनरावृति का कोई भी तरीका समान नियमों को शामिल करते हुए समान संख्या में कटौती चरणों की ओर ले जाता है (जब नियम b6 और b7 को समान माना जाता है)। की कमी <math>A(2,1)</math> उदाहरण के लिए 35 चरणों में परिवर्तित होता है: 12 × b1, 4 × b2, 1 × b3, 4 × b5, 12 × b6/b7, 1 × r9, 1 × r10। कार्यप्रणाली केवल उस क्रम को प्रभावित करती है जिसमें कटौती नियम लागू होते हैं।
*ये विचार केवल पुनरावर्तन गहराई से संबंधित हैं। पुनरावृति का कोई भी तरीका समान नियमों को शामिल करते हुए समान संख्या में कटौती चरणों की ओर ले जाता है (जब नियम b6 और b7 को समान माना जाता है)। की कमी <math>A(2,1)</math> उदाहरण के लिए 35 चरणों में परिवर्तित होता है: 12 × b1, 4 × b2, 1 × b3, 4 × b5, 12 × b6/b7, 1 × r9, 1 × r10। फलनप्रणाली केवल उस क्रम को प्रभावित करती है जिसमें कटौती नियम लागू होते हैं।
*निष्पादन समय का वास्तविक लाभ बार-बार उप-परिणामों की पुनर्गणना न करके ही प्राप्त किया जा सकता है। [[संस्मरण]] एक ऑप्टिमाइज़ेशन तकनीक है जहाँ फ़ंक्शन कॉल के परिणाम कैश किए जाते हैं और उसी इनपुट के फिर से आने पर वापस आ जाते हैं। उदाहरण के लिए देखें {{harvtxt|Ward|1993}}. {{harvtxt|Grossman|Zeitman|1988}} एक चालाक एल्गोरिदम प्रकाशित किया जो गणना करता है <math>A(i,n)</math> अंदर <math>\mathcal{O}(i A(i,n))</math> समय और भीतर <math>\mathcal{O}(i)</math> अंतरिक्ष।
*निष्पादन समय का वास्तविक लाभ बार-बार उप-परिणामों की पुनर्गणना न करके ही प्राप्त किया जा सकता है। [[संस्मरण]] एक ऑप्टिमाइज़ेशन तकनीक है जहाँ फलन कॉल के परिणाम कैश किए जाते हैं और उसी आगम के फिर से आने पर वापस आ जाते हैं। उदाहरण के लिए देखें {{harvtxt|वार्ड |1993}}. {{harvtxt|ग्रॉसमैन |जेटमन|1988}} एक चालाक कलन विधि प्रकाशित किया जो गणना करता है <math>A(i,n)</math> अंदर <math>\mathcal{O}(i A(i,n))</math> समय और भीतर <math>\mathcal{O}(i)</math> स्थान ।


=== बड़ी संख्या ===
===बड़ी संख्या===
यह प्रदर्शित करने के लिए कि की गणना कैसे की जाती है <math>A(4, 3)</math> कई चरणों में और बड़ी संख्या में परिणाम:<ref group="n" name="letop1"/>
यह प्रदर्शित करने के लिए कि की गणना कैसे की जाती है <math>A(4, 3)</math> कई चरणों में और बड़ी संख्या में परिणाम:<ref group="n" name="letop1" />  


:<math>\begin{align}
:<math>\begin{align}
Line 568: Line 573:




== मूल्यों की तालिका ==
==मानों की सारणी==
एकरमैन फ़ंक्शन की गणना एक अनंत तालिका के रूप में की जा सकती है। सबसे पहले, प्राकृतिक संख्याओं को शीर्ष पंक्ति में रखें। तालिका में संख्या निर्धारित करने के लिए, संख्या को तुरंत बाईं ओर ले जाएं। फिर उस संख्या का उपयोग उस संख्या और एक पंक्ति द्वारा दिए गए कॉलम में आवश्यक संख्या देखने के लिए करें। यदि इसके बाईं ओर कोई संख्या नहीं है, तो बस पिछली पंक्ति में 1 वाले कॉलम को देखें। यहाँ तालिका का एक छोटा ऊपरी-बाएँ भाग है:
एकरमैन फलन की गणना एक अनंत सारणी के रूप में की जा सकती है। सबसे पहले, प्राकृतिक संख्याओं को शीर्ष पंक्ति में रखें। सारणी में संख्या निर्धारित करने के लिए, संख्या को तुरंत बाईं ओर ले जाएं। फिर उस संख्या का उपयोग उस संख्या और एक पंक्ति द्वारा दिए गए स्तंभ में आवश्यक संख्या देखने के लिए करें। यदि इसके बाईं ओर कोई संख्या नहीं है, तो बस पिछली पंक्ति में 1 वाले स्तंभ को देखें। यहाँ सारणी का एक छोटा ऊपरी-बाएँ भाग है:


{| class="wikitable"
{| class="wikitable"
|+ Values of ''A''(''m'',&nbsp;''n'')
|+''A'' के मान (''m'',&nbsp;''n'')
|-
|-
! {{diagonal split header|''m''|''n''}}
! {{diagonal split header|''m''|''n''}}
! 0
!0
! 1
!1
! 2
!2
! 3
!3
! 4
!4
! ''n''
!''n''
|-
|-
! 0
!0
| 1 || 2 || 3 || 4 || 5 || <math>n + 1</math>
|1
|
2||3||4|| 5||<math>n + 1</math>
|-
|-
! 1
!1
| 2 || 3 || 4 || 5 || 6 || <math>n + 2 = 2 + (n + 3) - 3</math>
|2
|  
3|| 4|| 5||6||<math>n + 2 = 2 + (n + 3) - 3</math>
|-
|-
! 2
! 2
| 3 || 5 || 7 || 9 || 11 || <math>2n + 3 = 2\cdot(n + 3) - 3</math>
| 3
|
5||7|| 9||11 ||<math>2n + 3 = 2\cdot(n + 3) - 3</math>
|-
|-
! 3
!3
| 5 || 13 || 29 || 61 || 125 || <math>2^{(n + 3)} - 3</math>
| 5
|
13|| 29||61||125||<math>2^{(n + 3)} - 3</math>
|-
|-
! 4
!4
| 13 <br /><br /><math>={2^{2^{2}}}-3</math><br /><math>=2\uparrow\uparrow 3 - 3</math>
|13 <br /><br /><math>={2^{2^{2}}}-3</math><br /><math>=2\uparrow\uparrow 3 - 3</math>
| 65533 <br /><br /><math>={2^{2^{2^{2}}}}-3</math><br /><math>=2\uparrow\uparrow 4 - 3</math>
|65533 <br /><br /><math>={2^{2^{2^{2}}}}-3</math><br /><math>=2\uparrow\uparrow 4 - 3</math>
| 2<sup>65536</sup>&nbsp;−&nbsp;3 <br /><br /><math>={2^{2^{2^{2^{2}}}}}-3</math><br /><math>=2\uparrow\uparrow 5 - 3</math>
| 2<sup>65536</sup>&nbsp;−&nbsp;3 <br /><br /><math>={2^{2^{2^{2^{2}}}}}-3</math><br /><math>=2\uparrow\uparrow 5 - 3</math>
| <math>{2^{2^{65536}}} - 3</math> <br /><br /><math>={2^{2^{2^{2^{2^{2}}}}}}-3</math><br /><math>=2\uparrow\uparrow 6 - 3</math>
|<math>{2^{2^{65536}}} - 3</math> <br /><br /><math>={2^{2^{2^{2^{2^{2}}}}}}-3</math><br /><math>=2\uparrow\uparrow 6 - 3</math>
| <math>{2^{2^{2^{65536}}}} - 3</math> <br /><br /><math>={2^{2^{2^{2^{2^{2^{2}}}}}}}-3</math><br /><math>=2\uparrow\uparrow 7 - 3</math>
|<math>{2^{2^{2^{65536}}}} - 3</math> <br /><br /><math>={2^{2^{2^{2^{2^{2^{2}}}}}}}-3</math><br /><math>=2\uparrow\uparrow 7 - 3</math>
| <math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}}_{n+3} - 3\end{matrix}</math><br /><br /><math>=2\uparrow\uparrow (n+3) - 3</math>
|<math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}}_{n+3} - 3\end{matrix}</math><br /><br /><math>=2\uparrow\uparrow (n+3) - 3</math>
|-
|-
! 5
!5
| 65533 <br /><math>=2\uparrow\uparrow(2\uparrow\uparrow 2) - 3</math><br /><math>=2\uparrow\uparrow\uparrow 3 - 3</math>
|65533 <br /><math>=2\uparrow\uparrow(2\uparrow\uparrow 2) - 3</math><br /><math>=2\uparrow\uparrow\uparrow 3 - 3</math>
| <math>2\uparrow\uparrow\uparrow 4 - 3</math>
|<math>2\uparrow\uparrow\uparrow 4 - 3</math>
| <math>2\uparrow\uparrow\uparrow 5 - 3</math>
|<math>2\uparrow\uparrow\uparrow 5 - 3</math>
| <math>2\uparrow\uparrow\uparrow 6 - 3</math>
|<math>2\uparrow\uparrow\uparrow 6 - 3</math>
| <math>2\uparrow\uparrow\uparrow 7 - 3</math>
|<math>2\uparrow\uparrow\uparrow 7 - 3</math>
| <math>2\uparrow\uparrow\uparrow (n+3) - 3</math>
|<math>2\uparrow\uparrow\uparrow (n+3) - 3</math>
|-
|-
! 6
!6
| <math>2\uparrow\uparrow\uparrow\uparrow 3 - 3</math>
|<math>2\uparrow\uparrow\uparrow\uparrow 3 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 4 - 3</math>
|<math>2\uparrow\uparrow\uparrow\uparrow 4 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 5 - 3</math>
|<math>2\uparrow\uparrow\uparrow\uparrow 5 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 6 - 3</math>
|<math>2\uparrow\uparrow\uparrow\uparrow 6 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 7 - 3</math>
|<math>2\uparrow\uparrow\uparrow\uparrow 7 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow (n+3) - 3</math>
|<math>2\uparrow\uparrow\uparrow\uparrow (n+3) - 3</math>
|-
|-
! ''m''
!''m''
| <math>(2\to 3\to(m-2))-3</math>
|<math>(2\to 3\to(m-2))-3</math>
| <math>(2\to 4\to(m-2))-3</math>
|<math>(2\to 4\to(m-2))-3</math>
| <math>(2\to 5\to(m-2))-3</math>
|<math>(2\to 5\to(m-2))-3</math>
| <math>(2\to 6\to(m-2))-3</math>
|<math>(2\to 6\to(m-2))-3</math>
| <math>(2\to 7\to(m-2))-3</math>
|<math>(2\to 7\to(m-2))-3</math>
| <math>(2\to(n+3)\to(m-2))-3</math>
|<math>(2\to(n+3)\to(m-2))-3</math>
|}
|}
यहां संख्याएं जो केवल रिकर्सिव एक्सपोनेंटिएशन या नुथ के अप-एरो नोटेशन के साथ व्यक्त की जाती हैं, बहुत बड़ी हैं और सादे दशमलव अंकों में नोट करने के लिए बहुत अधिक जगह लेती हैं।
यहां संख्याएं जो केवल पुनरावर्ती घातांकीय या नुथ के उच्च-तीर संकेतन के साथ व्यक्त की जाती हैं, जो कि बहुत बड़ी होती हैं और दशमलव अंक प्रणाली में लिखने के लिए बहुत अधिक स्थान लेती हैं।


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


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


{| class="wikitable"
{| class="wikitable"
|+ Values of ''A''(''m'',&nbsp;''n'')
|+''A'' के मान (''m'',&nbsp;''n'')
|-
|-
! {{diagonal split header|''m''|''n''}}
! {{diagonal split header|''m''|''n''}}
! 0
!0
! 1
!1
! 2
!2
! 3
!3
! 4
!4
! ''n''
!''n''
|-
|-
! 0
!0
| 0+1 || 1+1 || 2+1 || 3+1 || 4+1 || ''n'' + 1
| 0+1||1+1||2+1||3+1||4+1 ||''n'' + 1
|-
|-
! 1
!1
| ''A''(0, 1) || ''A''(0, ''A''(1, 0))<br />= ''A''(0, 2) || ''A''(0, ''A''(1, 1))<br />= ''A''(0, 3) || ''A''(0, ''A''(1, 2))<br />= ''A''(0, 4) || ''A''(0, ''A''(1, 3))<br />= ''A''(0, 5) || ''A''(0, ''A''(1, ''n''−1))
|''A''(0, 1)||''A''(0, ''A''(1, 0))<br />= ''A''(0, 2)||''A''(0, ''A''(1, 1))<br />= ''A''(0, 3)||''A''(0, ''A''(1, 2))<br />= ''A''(0, 4)||''A''(0, ''A''(1, 3))<br />= ''A''(0, 5)||''A''(0, ''A''(1, ''n''−1))
|-
|-
! 2
!2
| ''A''(1, 1) || ''A''(1, ''A''(2, 0))<br />= ''A''(1, 3) || ''A''(1, ''A''(2, 1))<br />= ''A''(1, 5) || ''A''(1, ''A''(2, 2))<br />= ''A''(1, 7) || ''A''(1, ''A''(2, 3))<br />= ''A''(1, 9) || ''A''(1, ''A''(2, ''n''−1))
|''A''(1, 1)||''A''(1, ''A''(2, 0))<br />= ''A''(1, 3)||''A''(1, ''A''(2, 1))<br />= ''A''(1, 5)||''A''(1, ''A''(2, 2))<br />= ''A''(1, 7)||''A''(1, ''A''(2, 3))<br />= ''A''(1, 9)||''A''(1, ''A''(2, ''n''−1))
|-
|-
! 3
!3
| ''A''(2, 1) || ''A''(2, ''A''(3, 0))<br />= ''A''(2, 5) || ''A''(2, ''A''(3, 1))<br />= ''A''(2, 13) || ''A''(2, ''A''(3, 2))<br />= ''A''(2, 29) || ''A''(2, ''A''(3, 3))<br />= ''A''(2, 61) || ''A''(2, ''A''(3, ''n''−1))
|''A''(2, 1)||''A''(2, ''A''(3, 0))<br />= ''A''(2, 5)||''A''(2, ''A''(3, 1))<br />= ''A''(2, 13)||''A''(2, ''A''(3, 2))<br />= ''A''(2, 29)||''A''(2, ''A''(3, 3))<br />= ''A''(2, 61)||''A''(2, ''A''(3, ''n''−1))
|-
|-
! 4
!4
| ''A''(3, 1) || ''A''(3, ''A''(4, 0))<br />= ''A''(3, 13) || ''A''(3, ''A''(4, 1))<br />= ''A''(3, 65533) || ''A''(3, ''A''(4, 2)) || ''A''(3, ''A''(4, 3)) || ''A''(3, ''A''(4, ''n''−1))
|''A''(3, 1)||''A''(3, ''A''(4, 0))<br />= ''A''(3, 13)||''A''(3, ''A''(4, 1))<br />= ''A''(3, 65533)||''A''(3, ''A''(4, 2))||''A''(3, ''A''(4, 3))||''A''(3, ''A''(4, ''n''−1))
|-
|-
! 5
! 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))
|''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
! 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''(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))
|}
|}




== गुण ==
==गुण==


=== सामान्य टिप्पणी ===
===सामान्य टिप्पणी===
*यह तुरंत स्पष्ट नहीं हो सकता है कि का मूल्यांकन <math>A(m, n)</math> हमेशा समाप्त होता है। हालाँकि, पुनरावर्तन बाध्य है क्योंकि प्रत्येक पुनरावर्ती अनुप्रयोग में या तो <math>m</math> घटता है, या <math>m</math> वही रहता है और <math>n</math> घटता है। हर बार कि <math>n</math> शून्य हो जाता है, <math>m</math> घटता है, इसलिए <math>m</math> अंततः शून्य भी हो जाता है। (अधिक तकनीकी रूप से व्यक्त, प्रत्येक मामले में जोड़ी <math>(m,n)</math> जोड़े पर शब्दकोष क्रम में घटता है, जो एक अच्छी तरह से क्रमित है, ठीक एकल गैर-ऋणात्मक पूर्णांकों के क्रम की तरह; इसका मतलब यह है कि कोई व्यक्ति लगातार कई बार क्रम में नीचे नहीं जा सकता है।) हालांकि, कब <math>m</math> घटता है कि कितना पर कोई ऊपरी सीमा नहीं है <math>n</math> बढ़ सकता है - और यह अक्सर बहुत बढ़ जाएगा।
*यह तुरंत स्पष्ट नहीं किया जा सकता है कि का मूल्यांकन <math>A(m, n)</math> हमेशा समाप्त हो चुका है। हालाँकि, पुनरावर्तन बाध्य है क्योंकि प्रत्येक पुनरावर्ती अनुप्रयोग में या तो <math>m</math> घटता है, या फिर <math>m</math> वही रहता है और <math>n</math> घटता है। हर बार यदि <math>n</math> शून्य हो जाता है, तो <math>m</math> घटता है, इसलिए <math>m</math> अंततः शून्य हो जाता है। (अधिक तकनीकी रूप से व्यक्त, प्रत्येक मामले में जोड़ी <math>(m,n)</math> जोड़े पर शब्दकोष क्रम में घटता है, जो एक अच्छी तरह से क्रमित है, ठीक एकल ऋणोतर पूर्णांकों के क्रम की तरह; इसका मतलब यह है कि कोई व्यक्ति लगातार कई बार क्रम में नीचे नहीं जा सकता है।) हालांकि, <math>m</math> कब घटता है और कितना इस पर कोई ऊपरी सीमा निर्धारित नहीं है कि  <math>n</math> कितना बढ़ सकता है - और यह अक्सर बहुत बढ़ जाता है ।
*1, 2, या 3 जैसे m के छोटे मानों के लिए, एकरमैन फ़ंक्शन n के संबंध में अपेक्षाकृत धीमी गति से बढ़ता है (अधिकतम [[घातीय वृद्धि]] पर)। के लिये <math>m\geq 4</math>हालाँकि, यह बहुत अधिक तेज़ी से बढ़ता है; यहाँ तक की <math>A(4,2)</math> लगभग 2 है{{e|19728}}, और का दशमलव विस्तार <math>A(4, 3)</math> किसी भी विशिष्ट माप से बहुत बड़ा है।
*1, 2, या 3 जैसे m के छोटे मानों के लिए, एकरमैन फलन n के संबंध में अपेक्षाकृत धीमी गति से बढ़ता है (अधिकतम [[घातीय वृद्धि]] पर)। हालाँकि  <math>m\geq 4</math> के लिये , यह बहुत अधिक तेज़ी से बढ़ता है; यहाँ तक की <math>A(4,2)</math> लगभग 2{{e|19728}}, और <math>A(4, 3)</math> का दशमलव विस्तार किसी भी विशिष्ट माप से बहुत बड़ा है।
*एक दिलचस्प पहलू यह है कि इसके द्वारा उपयोग किया जाने वाला एकमात्र अंकगणितीय ऑपरेशन 1 का जोड़ है। इसकी तेजी से बढ़ती शक्ति पूरी तरह से नेस्टेड पुनरावर्तन पर आधारित है। इसका तात्पर्य यह भी है कि इसके चलने का समय कम से कम इसके उत्पादन के अनुपात में है, और यह भी बहुत बड़ा है। वास्तविकता में, ज्यादातर मामलों में चलने का समय आउटपुट से कहीं बड़ा होता है; ऊपर देखो।
*एक दिलचस्प पहलू यह है कि इसके द्वारा उपयोग किया जाने वाला एकमात्र अंकगणितीय संक्रिया 1 का जोड़ है। इसकी तेजी से बढ़ती शक्ति पूरी तरह से नेस्टेड पुनरावर्तन पर आधारित है। इसका तात्पर्य यह भी है कि इसके गणना करने का समय कम से कम इसके गुणन के अनुपात में है, और यह भी बहुत बड़ा है। वास्तविकता में, ज्यादातर मामलों में गणना करने का समय निर्गम से कहीं बड़ा होता है; जैसा की ऊपर प्रदर्शित किया गया है।
* एक एकल-तर्क संस्करण <math>f(n)=A(n,n)</math> जो दोनों को बढ़ाता है <math>m</math> तथा <math>n</math> एक ही समय में प्रत्येक आदिम पुनरावर्ती कार्य को बौना कर देता है, जिसमें बहुत तेजी से बढ़ने वाले कार्य शामिल हैं जैसे कि घातीय कार्य, बहुउद्देशीय कार्य, बहु- और [[superactorial]] कार्य, और यहां तक ​​​​कि Knuth के अप-एरो नोटेशन का उपयोग करके परिभाषित फ़ंक्शन (अनुक्रमित अप-एरो को छोड़कर) प्रयोग किया जाता है)। यह देखा जा सकता है <math>f(n)</math> मोटे तौर पर तुलनीय है <math>f_{\omega}(n)</math> तेजी से बढ़ते पदानुक्रम में। यह दिखाने के लिए इस चरम वृद्धि का फायदा उठाया जा सकता है <math>f</math> जो स्पष्ट रूप से [[ट्यूरिंग मशीन]] जैसी अनंत मेमोरी वाली मशीन पर गणना योग्य है और इसलिए एक गणना योग्य कार्य है, किसी भी आदिम पुनरावर्ती कार्य की तुलना में तेजी से बढ़ता है और इसलिए आदिम पुनरावर्ती नहीं है।
*एक एकल-प्राचर संस्करण <math>f(n)=A(n,n)</math> जो दोनों <math>m</math> तथा <math>n</math> को बढ़ाता है एक ही समय में प्रत्येक मूल पुनरावर्ती फलन को बौना कर देता है, जिसमें बहुत तेजी से बढ़ने वाले फलन शामिल हैं जैसे कि घातीय फलन, बहुउद्देशीय फलन, बहु- और [[superactorial|सुपरफैक्टोरियल]] फलन, और यहां तक ​​​​कि क्नुथ के उच्च-तीर संकेतन का उपयोग करके परिभाषित फलन (अनुक्रमित उच्च-तीर को छोड़कर) प्रयोग किया जाता है)। यह देखा जा सकता है <math>f(n)</math> मोटे तौर पर तुलनीय है <math>f_{\omega}(n)</math> तेजी से बढ़ते पदानुक्रम में। यह दिखाने के लिए इस चरम वृद्धि का फायदा उठाया जा सकता है <math>f</math> जो स्पष्ट रूप से [[ट्यूरिंग मशीन]] जैसी अनंत मेमोरी वाली मशीन पर गणना योग्य है और इसलिए एक गणना योग्य फलन है, किसी भी मूल पुनरावर्ती फलन की तुलना में तेजी से बढ़ता है और इसलिए मूल पुनरावर्ती नहीं है।


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


एकरमैन फ़ंक्शन किसी भी आदिम पुनरावर्ती फ़ंक्शन की तुलना में तेज़ी से बढ़ता है और इसलिए स्वयं आदिम पुनरावर्ती नहीं है। सबूत का स्केच यह है: k रिकर्सन तक का उपयोग करके परिभाषित एक आदिम पुनरावर्ती फ़ंक्शन की तुलना में धीमी गति से बढ़ना चाहिए <math>f_{k+1}(n)</math>, (k+1)-th फ़ंक्शन तेजी से बढ़ते पदानुक्रम में, लेकिन एकरमैन फ़ंक्शन कम से कम उतनी ही तेज़ी से बढ़ता है <math>f_\omega(n)</math>.
विशेष रूप से, एक दिखाता है कि प्रत्येक मूल पुनरावर्ती फलन <math>f(x_1,\ldots,x_n)</math> के लिए एक ऋणोतर पूर्णांक <math>t</math> मौजूद है कि सभी ऋणोतर पूर्णांकों के लिए <math>x_1,\ldots,x_n</math>,


विशेष रूप से, एक दिखाता है कि प्रत्येक आदिम पुनरावर्ती कार्य के लिए <math>f(x_1,\ldots,x_n)</math> एक गैर-ऋणात्मक पूर्णांक मौजूद है <math>t</math> जैसे कि सभी गैर-ऋणात्मक पूर्णांकों के लिए <math>x_1,\ldots,x_n</math>,
:<math>f(x_1,\ldots,x_n)<A(t,\max_i x_i).</math>
एक बार यह स्थापित हो जाने के बाद, यह अनुसरण करता है कि  <math>A</math> स्वयं मूल पुनरावर्ती नहीं है, अन्यथा डालने के बाद से <math>x_1=x_2=t</math> विरोधाभास की ओर ले जाएगा <math>A(t,t)<A(t,t).</math>


:<math>f(x_1,\ldots,x_n)<A(t,\max_i x_i).</math>
सबूत<ref>{{Cite web|url=http://planetmath.org/ackermannfunctionisnotprimitiverecursive|title=एकरमैन फ़ंक्शन प्रिमिटिव रिकर्सिव {{!}} Planetmath.org नहीं है|last=Woo|first=Chi|date=2009-12-17|website=planetmath.org|language=en|archive-url= https://web.archive.org/web/20130509202634/http://planetmath.org/ackermannfunctionisnotprimitiverecursive|archive-date=2013-05-09|url-status=dead}}</ref> निम्नानुसार आगे बढ़ता है: सभी फलनों के लिए एक वर्ग <math>\mathcal{A}</math> को परिभाषित करें जो एकरमेन फलन की तुलना में धीमी गति से बढ़ता हो
एक बार यह स्थापित हो जाने के बाद, यह उसका अनुसरण करता है <math>A</math> स्वयं आदिम पुनरावर्ती नहीं है, अन्यथा डालने के बाद से <math>x_1=x_2=t</math> विरोधाभास की ओर ले जाएगा <math>A(t,t)<A(t,t).</math>
सबूत<ref>{{Cite web|url=http://planetmath.org/ackermannfunctionisnotprimitiverecursive|title=एकरमैन फ़ंक्शन प्रिमिटिव रिकर्सिव {{!}} Planetmath.org नहीं है|last=Woo|first=Chi|date=2009-12-17|website=planetmath.org|language=en|archive-url= https://web.archive.org/web/20130509202634/http://planetmath.org/ackermannfunctionisnotprimitiverecursive|archive-date=2013-05-09|url-status=dead}}</ref> निम्नानुसार आगे बढ़ता है: वर्ग को परिभाषित करें <math>\mathcal{A}</math> एकरमेन फ़ंक्शन की तुलना में धीमी गति से बढ़ने वाले सभी कार्यों में से


:<math>\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\} </math>
:<math>\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\} </math>
और दिखाओ <math>\mathcal{A}</math> सभी आदिम पुनरावर्ती कार्य शामिल हैं। उत्तरार्द्ध इसे दिखाकर हासिल किया जाता है <math>\mathcal{A}</math> इसमें निरंतर कार्य, उत्तराधिकारी कार्य, प्रक्षेपण कार्य शामिल हैं और यह कार्य रचना और आदिम पुनरावर्तन के संचालन के तहत बंद है।
और यह प्रदर्शित करे कि <math>\mathcal{A}</math> में सभी मूल पुनरावर्ती फलन शामिल हैं।उत्तरार्द्ध इसे दिखाकर हासिल किया जाता है <math>\mathcal{A}</math> इसमें निरंतर फलन, उत्तराधिकारी फलन, प्रक्षेपण फलन शामिल हैं और यह फलन रचना और मूल पुनरावर्तन के संचालन के तहत बंद है।


== उलटा ==
==प्रतिलोम==
समारोह के बाद से {{nowrap|1=&nbsp;''f''(''n'') = ''A''(''n'', ''n'')}} ऊपर माना गया बहुत तेजी से बढ़ता है, इसका उलटा कार्य, f{{i sup|−1}}, बहुत धीमी गति से बढ़ता है। यह व्युत्क्रम एकरमैन फ़ंक्शन ''f''<sup>−1</sup> को आमतौर पर ''α'' से दर्शाया जाता है। वास्तव में, ''α''(''n'') किसी भी व्यावहारिक इनपुट आकार ''n'' के लिए 5 से कम है, क्योंकि {{nowrap|''A''(4, 4)}} के आदेश पर है <math>2^{2^{2^{2^{16}}}}</math>.
फलन के बाद से {{nowrap|1=&nbsp;''f''(''n'') = ''A''(''n'', ''n'')}} ऊपर माना गया बहुत तेजी से बढ़ता है, इसका प्रतिलोम फलन, f{{i sup|−1}}, बहुत धीमी गति से बढ़ता है। यह प्रतिलोम एकरमैन फलन ''f''<sup>−1</sup> को आमतौर पर ''α'' से दर्शाया जाता है। वास्तव में, ''α''(''n'') किसी भी व्यावहारिक आगम आकार ''n'' के लिए 5 से कम है, क्योंकि {{nowrap|''A''(4, 4)}} के आदेश पर है <math>2^{2^{2^{2^{16}}}}</math>


यह व्युत्क्रम कुछ एल्गोरिदम के समय [[कम्प्यूटेशनल जटिलता सिद्धांत]] में प्रकट होता है, जैसे कि अलग-अलग सेट डेटा संरचना और [[बर्नार्ड चाज़ेल]] के [[कलन विधि]] न्यूनतम फैले हुए पेड़ों के लिए। कभी-कभी इन सेटिंग्स में एकरमैन के मूल कार्य या अन्य विविधताओं का उपयोग किया जाता है, लेकिन वे सभी समान उच्च दर से बढ़ते हैं। विशेष रूप से, कुछ संशोधित फ़ंक्शन -3 और इसी तरह की शर्तों को हटाकर अभिव्यक्ति को सरल बनाते हैं।
यह प्रतिलोम कुछ कलन विधि के समय [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणना जटिलता सिद्धांत]] में दिखाई देता है, जैसे कि न्यूनतम स्पैन्मिंग ट्री के लिए चैजेलल कलन विधि। कभी-कभी इन सेटिंग्स में एकरमैन के मूल फलन या अन्य प्रकार की वस्तुएं इन सेटिंग्स में प्रयोग की जाती है, ये सभी समान रूप से उच्च दर पर बढ़ती हैं। विशेष रूप से, कुछ संशोधित फलन, -3 और इसी तरह की शर्तों को हटाकर अभिव्यक्ति को सरल बनाते हैं।


व्युत्क्रम एकरमैन फ़ंक्शन के दो-पैरामीटर भिन्नता को निम्नानुसार परिभाषित किया जा सकता है, जहां <math>\lfloor x \rfloor</math> मंजिल समारोह है:
प्रतिलोम एकरमैन फलन के दो-पैरामीटर रूपांतर को निम्नानुसार परिभाषित किया जा सकता है, जहां <math>\lfloor x \rfloor</math> फ्लोर फलन है:


:<math>\alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}.</math>
:<math>\alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}.</math>
यह कार्य ऊपर उल्लिखित एल्गोरिदम के अधिक सटीक विश्लेषण में उत्पन्न होता है, और अधिक परिष्कृत समय सीमा प्रदान करता है। असम्बद्ध-सेट डेटा संरचना में, एम संचालन की संख्या का प्रतिनिधित्व करता है जबकि एन तत्वों की संख्या का प्रतिनिधित्व करता है; मिनिमम स्पैनिंग ट्री एल्गोरिथम में, m किनारों की संख्या का प्रतिनिधित्व करता है जबकि n वर्टिकल की संख्या का प्रतिनिधित्व करता है। की कई थोड़ी अलग परिभाषाएँ {{nowrap|''α''(''m'', ''n'')}} मौजूद; उदाहरण के लिए, {{nowrap|log<sub>2</sub> ''n''}} कभी-कभी n द्वारा प्रतिस्थापित किया जाता है, और कभी-कभी फर्श फ़ंक्शन को [[छत समारोह]] द्वारा प्रतिस्थापित किया जाता है।
यह फलन ऊपर उल्लिखित कलन विधि के अधिक सटीक विश्लेषण में उत्पन्न होता है, और अधिक परिष्कृत समय सीमा प्रदान करता है। असम्बद्ध-समूह डेटा संरचना में, एम संचालन की संख्या का प्रतिनिधित्व करता है जबकि एन तत्वों की संख्या का प्रतिनिधित्व करता है; मिनिमम स्पैनिंग ट्री एल्गोरिथम में, m किनारों की संख्या का प्रतिनिधित्व करता है जबकि n वर्टिकल की संख्या का प्रतिनिधित्व करता है। की कई थोड़ी अलग परिभाषाएँ {{nowrap|''α''(''m'', ''n'')}} मौजूद; उदाहरण के लिए, {{nowrap|log<sub>2</sub> ''n''}} कभी-कभी n द्वारा प्रतिस्थापित किया जाता है, और कभी-कभी फर्श फलन को [[छत समारोह|फ्लोर फलन]] द्वारा प्रतिस्थापित किया जाता है।


अन्य अध्ययन एक के व्युत्क्रम कार्य को परिभाषित कर सकते हैं जहां m एक स्थिरांक पर सेट है, जैसे कि व्युत्क्रम किसी विशेष पंक्ति पर लागू होता है। {{sfn|Pettie|2002}}
अन्य अध्ययन एक के प्रतिलोम फलन को परिभाषित कर सकते हैं जहां m एक स्थिरांक पर समूह है, जैसे कि प्रतिलोम किसी विशेष पंक्ति पर लागू होता है। {{sfn|Pettie|2002}}
एकरमैन फ़ंक्शन का व्युत्क्रम आदिम पुनरावर्ती है।{{sfn|Matos|2014}}
एकरमैन फलन का प्रतिलोम मूल पुनरावर्ती है।{{sfn|Matos|2014}}




== बेंचमार्क के रूप में प्रयोग करें ==
==बेंचमार्क के रूप में प्रयोग करें ==
एकरमैन फ़ंक्शन, अत्यधिक गहरी रिकर्सन के संदर्भ में इसकी परिभाषा के कारण, रिकर्सन को अनुकूलित करने के लिए [[संकलक]] की क्षमता के बेंचमार्क के रूप में उपयोग किया जा सकता है। इस तरह से एकरमैन के कार्य का पहला प्रकाशित उपयोग 1970 में ड्रैगोस वैदा द्वारा किया गया था।{{sfn|Vaida|1970}} और, लगभग एक साथ, 1971 में, येंगवे सुंदब्लाड द्वारा।{{sfn|Sundblad|1971}}
एकरमैन फलन, अत्यधिक गहरी पुनरावर्ती के संदर्भ में इसकी परिभाषा के कारण, पुनरावर्ती को अनुकूलित करने के लिए [[संकलक]] की क्षमता के बेंचमार्क के रूप में उपयोग किया जा सकता है। इस तरह से एकरमैन के फलन का पहला प्रकाशित उपयोग 1970 में ड्रैगोस वैदा द्वारा किया गया था।{{sfn|Vaida|1970}} और, लगभग एक साथ, 1971 में, येंगवे सुंदब्लाड द्वारा।{{sfn|Sundblad|1971}}
1975 और 1982 के बीच लिखे गए पत्रों की एक त्रयी में ब्रायन विचमैन ([[वेटस्टोन (बेंचमार्क)]] के सह-लेखक) द्वारा सुंदरब्लैड का मौलिक पेपर लिया गया था।{{sfn|Wichmann|1976}}{{sfn|Wichmann|1977}}{{sfn|Wichmann|1982}}
1975 और 1982 के बीच लिखे गए पत्रों की एक त्रयी में ब्रायन विचमैन ([[वेटस्टोन (बेंचमार्क)]] के सह-लेखक) द्वारा सुंदरब्लैड का मौलिक पेपर लिया गया था।{{sfn|Wichmann|1976}}{{sfn|Wichmann|1977}}{{sfn|Wichmann|1982}}




== यह भी देखें ==
==यह भी देखें==  
<!-- keep alphabetical -->
<!-- keep alphabetical -->
* कम्प्यूटेबिलिटी सिद्धांत
*संगणनीयता सिद्धांत
* [[डबल रिकर्सन]]
*[[डबल रिकर्सन|डबल पुनरावर्ती]]
* तेजी से बढ़ती पदानुक्रम
*तेजी से बढ़ती पदानुक्रम
* [[गुडस्टीन समारोह]]
*[[गुडस्टीन समारोह|गुडस्टीन फलन]]
* आदिम पुनरावर्ती कार्य
*मूल पुनरावर्ती फलन
* [[रिकर्सन (कंप्यूटर विज्ञान)]]
*[[रिकर्सन (कंप्यूटर विज्ञान)|पुनरावर्ती (कंप्यूटर विज्ञान)]]
<!-- keep alphabetical -->
<!-- keep alphabetical -->


Line 725: Line 738:




==ग्रन्थसूची==
==ग्रन्थसूची ==
{{Refbegin}}
{{Refbegin}}
*{{cite journal
*{{cite journal
Line 1,027: Line 1,040:




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


*संगणनीयता सिद्धांत
*संगणनीयता सिद्धांत
*कुल समारोह
*पूर्ण फलन
*सूडान समारोह
*सूडान फलन
*योग
*योग
*प्रत्यावर्तन
*प्रत्यावर्तन
*पुनरावृत्त समारोह
*पुनरावृत्त फलन
*समारोह रचना
*फलन रचना
*जोड़नेवाला
*जोड़नेवाला
*ढेर (सार डेटा प्रकार)
* स्टैक (सार डेटा प्रकार)
*अच्छी तरह से आदेश
*अच्छी तरह से आदेश
*लेक्सिकोग्राफिक ऑर्डर
*लेक्सिकोग्राफिक ऑर्डर
*घातांक प्रकार्य
*घातांक प्रफलन
*तेजी से बढ़ने वाला पदानुक्रम
*तेजी से बढ़ने वाला पदानुक्रम
*उलटा काम करना
*प्रतिलोम काम करना
*न्यूनतम फैलाव वाला पेड़
*न्यूनतम फैलाव वाला पेड़
*असंयुक्त-सेट डेटा संरचना
*असंयुक्त-समूह डेटा संरचना
*फर्श समारोह
*फर्श फलन
==बाहरी संबंध==
==बाहरी संबंध==
* {{springer|title=Ackermann function|id=p/a120110|mode=cs1}}
*{{springer|title=Ackermann function|id=p/a120110|mode=cs1}}
* {{MathWorld | urlname = AckermannFunction | title = Ackermann function}}
*{{MathWorld | urlname = AckermannFunction | title = Ackermann function}}
* {{DADS|Ackermann's function|ackermann}}
*{{DADS|Ackermann's function|ackermann}}
* [http://www.gfredericks.com/main/sandbox/arith/ackermann An animated Ackermann function calculator]
*[http://www.gfredericks.com/main/sandbox/arith/ackermann An animated Ackermann function calculator]
* [http://timkoop.com/koop_loop_ackermanns_function_as_a_for_loop Ackerman function implemented using a for loop]
*[http://timkoop.com/koop_loop_ackermanns_function_as_a_for_loop Ackerman function implemented using a for loop]
* [[Scott Aaronson]], ''[http://www.scottaaronson.com/writings/bignumbers.html Who can name the biggest number?]'' (1999)
*[[Scott Aaronson]], ''[http://www.scottaaronson.com/writings/bignumbers.html Who can name the biggest number?]'' (1999)
* [http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm Ackermann functions]. Includes a table of some values.
*[http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm Ackermann functions]. Includes a table of some values.
* [http://forum.wolframscience.com/showthread.php?s=&threadid=579 Hyper-operations: Ackermann's Function and New Arithmetical Operation]
*[http://forum.wolframscience.com/showthread.php?s=&threadid=579 Hyper-operations: Ackermann's Function and New Arithmetical Operation]
* [http://www.mrob.com/pub/math/largenum.html Robert Munafo's Large Numbers] describes several variations on the definition of ''A''.
*[http://www.mrob.com/pub/math/largenum.html Robert Munafo's Large Numbers] describes several variations on the definition of ''A''.
* Gabriel Nivasch, [https://web.archive.org/web/20070821224819/http://yucs.org/~gnivasch/alpha/index.html Inverse Ackermann without pain] on the inverse Ackermann function.
*Gabriel Nivasch, [https://web.archive.org/web/20070821224819/http://yucs.org/~gnivasch/alpha/index.html Inverse Ackermann without pain] on the inverse Ackermann function.
* Raimund Seidel, ''[http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf Understanding the inverse Ackermann function]'' (PDF presentation).
*Raimund Seidel, ''[http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf Understanding the inverse Ackermann function]'' (PDF presentation).
* [http://rosettacode.org/wiki/Ackermann_Function The Ackermann function written in different programming languages], (on [[Rosetta Code]])
*[http://rosettacode.org/wiki/Ackermann_Function The Ackermann function written in different programming languages], (on [[Rosetta Code]])
* [http://www.geocities.com/hjsmithh/Ackerman/index.html Ackermann's Function] ([https://web.archive.org/web/20091026171012/http://www.geocities.com/hjsmithh/Ackerman/index.html Archived] 2009-10-24)—Some study and programming by Harry J. Smith.
*[http://www.geocities.com/hjsmithh/Ackerman/index.html Ackermann's Function] ([https://web.archive.org/web/20091026171012/http://www.geocities.com/hjsmithh/Ackerman/index.html Archived] 2009-10-24)—Some study and programming by Harry J. Smith.


{{Hyperoperations}}
{{Hyperoperations}}
{{Large numbers}}
{{Large numbers}}
{{Authority control}}
{{Authority control}}
[[Category:अंकगणित]]
[[Category:बड़े पूर्णांक]]
[[Category:विशेष कार्य]]
[[Category:गणना का सिद्धांत]]
[[Category: संगणनीयता सिद्धांत]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Created On 30/11/2022]]
[[Category:Articles with invalid date parameter in template]]
[[Category:Articles with short description]]
[[Category:CS1]]
[[Category:CS1 English-language sources (en)]]
[[Category:CS1 français-language sources (fr)]]
[[Category:CS1 maint]]
[[Category:CS1 Ελληνικά-language sources (el)]]
[[Category:Citation Style 1 templates|W]]
[[Category:Collapse templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates based on the Citation/CS1 Lua module]]
[[Category:Templates generating COinS|Cite web]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates used by AutoWikiBrowser|Cite web]]
[[Category:Templates using TemplateData]]
[[Category:Use shortened footnotes from November 2022]]
[[Category:Wikipedia fully protected templates|Cite web]]
[[Category:Wikipedia metatemplates]]

Latest revision as of 10:02, 29 December 2022

संगणनीयता सिद्धांत में, विल्हेम एकरमैन के नाम पर एकरमैन फलन, जो सबसे सरल फलन में से एक है[1] और सबसे पहले खोजे गए पूर्ण संगणनीय फलन का उदाहरण है जो कि मूल पुनरावर्ती फलन नहीं हैं। सभी मूल पुनरावर्ती फलन पूर्ण और संगणनीय हैं, लेकिन एकरमैन फलन यह दर्शाता है कि सभी पूर्ण संगणनीय फलन मूल फलन की पुनरावर्ती नहीं हैं। एकरमैन के प्रकाशन के बाद[2] उनके फलन के (जिसमें तीन ऋणोतर पूर्णांक प्राचर थे), कई लेखकों ने इसे विभिन्न उद्देश्यों के अनुरूप संशोधित किया, ताकि एकरमैन फलन मूल फलन के कई रूपों में से किसी को भी संदर्भित कर सके। एक सामान्य संस्करण, दो-प्राचर एकरमैन-पीटर फलन को ऋणोतर पूर्णांक m और n के लिए निम्नानुसार परिभाषित किया गया है:

छोटे आगम के लिए भी इसका मान तेजी से बढ़ता है। उदाहरण के लिए, A(4, 2) 19,729 दशमलव अंकों का पूर्णांक है[3] ( 265536−3 के बराबर, अथवा 22222−3).

इतिहास

1920 के दशक के अंत में, गणितज्ञ गेब्रियल सूडान और विल्हेम एकरमैन, डेविड हिल्बर्ट के छात्र, संगणना की नींव का अध्ययन कर रहे थे। सूडान और एकरमैन दोनों को पूर्ण संगणनीय फलन की खोज के लिए श्रेय दिया जाता है[4] (जिसे कुछ संदर्भों में केवल "पुनरावर्ती" कहा जाता है) जो मूल पुनरावर्ती फलन नहीं हैं। सूडान ने कम प्रसिद्ध सूडान फलन प्रकाशित किया, फिर कुछ ही समय बाद और स्वतंत्र रूप से, 1928 में, एकरमैन ने अपना फलन (ग्रीक अक्षर फ़ाई) प्रकाशित किया। एकरमैन का तीन-प्राचर फलन, , को इस तरह से परिभाषित किया गया है कि यह जैसे , के लिए और यह योग, गुणन और घातांक के बुनियादी परिचालनों का पुनरावृत्त करता है।

और P > 2 के लिए यह इस तरह के बुनियादी परिचालनों को बढ़ाता है जिसकी तुलना अतिसंचालन से की जा सकती है:

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

डेविड हिल्बर्ट ने परिकल्पना की कि एकरमैन फलन अनंत पर,[5] मूल पुनरावर्ती नहीं था, लेकिन यह एकरमैन, हिल्बर्ट के निजी सचिव और पूर्व छात्र थे, जिन्होंने वास्तव में अपने कागज में वास्तविक संख्या के निर्माण पर परिकल्पना को सिद्ध किया था।[2][6]

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

सामान्यीकृत अतिसंचालन, उदाहरण - , एकरमैन फलन का भी एक संस्करण है।[9]

1963 में आर.सी. बक अतिसंचालन सीक्वेंस पर एक सहज ज्ञान युक्त दो-चर [n 1]वेरिएंट पर आधारित है:[10][11]

अधिकांश अन्य संस्करणों की तुलना में बक के फलन में कोई अनावश्यक ऑफ़सेट नहीं है:

एकरमैन फलन के कई अन्य संस्करणों का अन्वेषण भी किया गया है।[12]

परिभाषा

परिभाषा: एम-सरणी फलन के रूप में

एकरमैन का मूल तीन-प्राचर फलन ऋणोतर पूर्णांकों तथा के लिए निम्नानुसार पुनरावर्तन परिभाषित किया गया है :

विभिन्न दो-प्राचर संस्करणों में से, पेटर और रॉबिन्सन द्वारा विकसित एक (जिसे अधिकांश लेखकों द्वारा एकरमैन फलन कहा जाता है) को ऋणोतर पूर्णांकों तथा के लिए निम्नलिखित अनुसार परिभाषित किया गया है :

एकरमेन फलन को अतिसंचालन अनुक्रम के संबंध में भी व्यक्त किया गया है:[13][14]

या, नुथ के उच्च-तीर संकेतन में लिखा गया है (पूर्णांक सूचकांक में बढ़ाया गया ):
या, समतुल्य रूप से, बक के फलन F के संदर्भ में:[10]
परिभाषा: पुनरावृत्त 1-सरणी फलन के रूप में परिभाषित करना

के n-वें पुनरावृति के रूप में :

पुनरावृत्त फलन एक निश्चित संख्या में स्वयं के साथ एक फलन बनाने की प्रक्रिया है। फलन रचना एक साहचर्य संक्रिया है, इसलिए .

एकरमैन फलन को एकल फलन के अनुक्रम के रूप में समझा जा सकता है ,यदि हम यह स्थापित कर सके कि .

तब फलन एक एकल [n 2] फलन का अनुक्रम ,होगा जिसे हम पुनरावृत्त फलन से पारिभाषित कर सकते है :


संगणना

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

टीआरएस, 2-सरणी फलन पर आधारित है

2-सरणी एकरमैन फलन की परिभाषा स्पष्ट कटौती नियम की ओर ले जाती है [15][16]

उदाहरण

गणना करने पर

कमी अनुक्रम है [n 3]

बाएँ सबसे बाहरी (एक कदम) नीतिबद्ध:             बांयी ओर-अंतरतम (एक-चरणीय) नीतिबद्ध:
         
         
         
         
         
         

गणना करना कोई स्टैक (अमूर्त डेटा प्रकार) का उपयोग कर सकता है, जिसमें प्रारंभ में तत्व होते हैं .

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

योजनाबद्ध रूप से, से शुरू :

WHILE stackLength <> 1
{
   POP 2 elements;
   PUSH 1 or 2 or 3 elements, applying the rules r1, r2, r3
}

स्यूडोकोड प्रकाशित हो चुकी है। ग्रॉसमैन & जेटमन (1988).

उदाहरण के लिए, आगम पर ,

स्टैक का विन्यास     कमी को दर्शाना [n 5]
         
         
         
         
         
         
         
         
         
         
         
         
         
         

टिप्पणियां

  • रोसेटा कोड पर 225 कंप्यूटर भाषाओं में सबसे बांयी ओर-अंतरतम नीति लागू की गई है।
  • सभी की गणना के लिए फलन कदम से अधिक नहीं लेता है[17]
  • ग्रॉसमैन & जेटमन (1988) बताया कि स्टैक की गणना में अधिकतम लंबाई , है जब कि .
उनका अपना कलन विधि, स्वाभाविक रूप से पुनरावृत्त, गणना करता है अंदर समय और भीतर स्थान ।
टीआरएस, पुनरावृत्त 1-सरणी फलन पर आधारित है

पुनरावृत्त 1-सरणी एकरमैन फलन की परिभाषा विभिन्न कमी नियमों की ओर ले जाती है

जैसा कि फलन रचना साहचर्य है, नियम r6 के बजाय परिभाषित किया जा सकता है

पिछले खंड की तरह की गणना स्टैक के साथ लागू किया जा सकता है।

प्रारंभ में स्टैक में तीन तत्व होते हैं .

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

योजनाबद्ध रूप से, से शुरू :

WHILE stackLength <> 1
{
   POP 3 elements;
   PUSH 1 or 3 or 5 elements, applying the rules r4, r5, r6;
}

उदाहरण

आगम पर क्रमिक स्टैक विन्यास हैं

संगत समानताएं हैं

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

क्रमिक स्टैक कॉन्फ़िगरेशन तब होगा

संगत समानताएं हैं

टिप्पणियां

  • किसी दिए गए आगम पर अब तक प्रस्तुत टीआरएस ने अभी तक चरणों की एक ही संख्या में एकजुट किया है। वे समान कटौती नियमों का भी उपयोग करते हैं (इस तुलना में नियमों r1, r2, r3 को क्रमशः नियम r4, r5, r6/r7 के समान माना जाता है)। उदाहरण के लिए, एक की कटौती 14 चरणों में अभिसरित होता है: 6 × r1, 3 × r2, 5 × r3। की कमी समान 14 चरणों में अभिसरित होता है: 6 × r4, 3 × r5, 5 × r6/r7। टीआरएस उस क्रम में भिन्न होते हैं जिसमें कमी के नियम लागू होते हैं।
  • कब नियमों का पालन करते हुए {r4, r5, r6} गणना की जाती है, स्टैक की अधिकतम लंबाई के नीचे रहती है जब कमी नियम r6 के स्थान पर कमी नियम r7 का उपयोग किया जाता है, तो स्टैक की अधिकतम लंबाई केवल होती है। स्टैक की लंबाई पुनरावर्ती गहराई को दर्शाती है। नियमों के अनुसार कमी के रूप में {r4, r5, r7} में पुनरावर्तन की एक छोटी अधिकतम गहराई शामिल है,[n 6] यह गणना उस संबंध में अधिक कुशल है।

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

जैसा सुंदब्लाड (1971) - या पोर्टो & माटोस (1980) - स्पष्ट रूप से दिखाया गया है, एकरमेन फलन अतिसंचालन अनुक्रम के संदर्भ में व्यक्त किया जा सकता है:

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

बक का फलन ,[10] एकरमैन फलन का एक भिन्न रूप, जिसकी गणना निम्न कमी नियमों के साथ की जा सकती है:

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

एकरमैन फलन की गणना करने के लिए तीन कटौती नियमों को जोड़ना पर्याप्त है

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

उदाहरण

गणना करना

कमी नियम के उपयोग से :[n 5]     कमी नियम के उपयोग से :[n 5]
         
         
         
         
         
         
                   
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         

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

  • जब टीआरएस कटौती नियम के साथ लागू की गई है: