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

From Vigyanwiki
No edit summary
No edit summary
 
(19 intermediate revisions by 4 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 12: 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>2222</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>, के लिए और यह योग, [[गुणा|गुणन]] और [[घातांक]] के बुनियादी परिचालनों का पुनरावृत्त करता है।


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


अनंत पर,{{sfn|Hilbert|1926|p=185}} डेविड हिल्बर्ट ने परिकल्पना की कि एकरमैन फलन मूल पुनरावर्ती नहीं था, लेकिन यह एकरमैन, हिल्बर्ट के निजी सचिव और पूर्व छात्र थे, जिन्होंने वास्तव में अपने कागज में वास्तविक संख्या के निर्माण पर परिकल्पना को सिद्ध किया था।{{sfn|Ackermann|1928}}{{sfn|van Heijenoort|1977}}
डेविड हिल्बर्ट ने परिकल्पना की कि एकरमैन फलन अनंत पर,{{sfn|Hilbert|1926|p=185}} मूल पुनरावर्ती नहीं था, लेकिन यह एकरमैन, हिल्बर्ट के निजी सचिव और पूर्व छात्र थे, जिन्होंने वास्तव में अपने कागज में वास्तविक संख्या के निर्माण पर परिकल्पना को सिद्ध किया था।{{sfn|Ackermann|1928}}{{sfn|van Heijenoort|1977}}


पीटर रोजसा{{sfn|Péter|1935}} और [[राफेल रॉबिन्सन]]{{sfn|Robinson|1948}}  ने बाद में एकरमैन फलन का एक दो-चर संस्करण को विकसित किया जो बाद में लगभग सभी लेखकों द्वारा पसंद किया गया।
पीटर रोजसा{{sfn|Péter|1935}} और [[राफेल रॉबिन्सन]]{{sfn|Robinson|1948}}  ने बाद में एकरमैन फलन का एक दो-चर संस्करण को विकसित किया जो बाद में लगभग सभी लेखकों द्वारा पसंद किया गया।


सामान्यीकृत अतिसंचालन, उदाहरण - <math>G(m, a, b) = a[m]b</math>, एकरमैन फलन का भी एक संस्करण है।{{sfn|Ritchie|1965|p=1028}}
सामान्यीकृत अतिसंचालन, उदाहरण - <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>वेरिएंट F पर आधारित है:{{sfn|Buck|1963}}{{sfn|Meeussen|Zantema|1992|p=6}}
 
1963 में आर.सी. बक अतिसंचालन सीक्वेंस पर एक सहज ज्ञान युक्त दो-चर <ref name="letop3" group="n">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>
अधिकांश अन्य संस्करणों की तुलना में बक के फलन में कोई अनावश्यक ऑफ़सेट नहीं है:
अधिकांश अन्य संस्करणों की तुलना में बक के फलन में कोई अनावश्यक ऑफ़सेट नहीं है:
Line 49: Line 51:
एकरमैन फलन के कई अन्य संस्करणों का अन्वेषण भी किया गया है।{{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 59: 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>  
\begin{array}{lcl}
\begin{array}{lcl}
\operatorname{A}(0, n) & = & n + 1 \\
\operatorname{A}(0, n) & = & n + 1 \\
Line 68: 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}
\operatorname{A}_{0}(n) & = & n+1 \\
\operatorname{A}_{0}(n) & = & n+1 \\
Line 104: Line 106:


==संगणना==
==संगणना==
एकरमैन फलन की पुनरावर्ती परिभाषा को स्वाभाविक रूप से [[पुनर्लेखन]] | टर्म पुनर्लेखन प्रणाली (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}
\text{(r1)} & A(0,n)      & \rightarrow & S(n) \\
\text{(r1)} & A(0,n)      & \rightarrow & S(n) \\
Line 117: 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 158: 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>
Line 216: Line 219:
|{{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}
\text{(r4)} & A(S(0),0,n)    & \rightarrow & S(n) \\
\text{(r4)} & A(S(0),0,n)    & \rightarrow & S(n) \\
Line 237: 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 248: 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 275: 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 315: 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 332: 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 \\
Line 343: Line 349:
या, बक के फलन के संदर्भ में, पैरामीटर सूची से निरंतर 2 को हटाने के बाद
या, बक के फलन के संदर्भ में, पैरामीटर सूची से निरंतर 2 को हटाने के बाद
    
    
::: <math> = \begin{cases}
:::<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>
बक का फलन <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}
\text{(b1)} & F(S(0),0,n)          & \rightarrow & S(n) \\
\text{(b1)} & F(S(0),0,n)          & \rightarrow & S(n) \\
Line 365: Line 371:
</math>
</math>
एकरमैन फलन की गणना करने के लिए तीन कटौती नियमों को जोड़ना पर्याप्त है
एकरमैन फलन की गणना करने के लिए तीन कटौती नियमों को जोड़ना पर्याप्त है
: <math>  
:<math>  
\begin{array}{lll}
\begin{array}{lll}
\text{(r8)}  & A(0,n)     & \rightarrow & S(n) \\
\text{(r8)}  & A(0,n)     & \rightarrow & S(n) \\
Line 372: Line 378:
\end{array}
\end{array}
</math>
</math>
ये नियम बेस केस (0, एन), संरेखण (एन + 3) और फज (-3) का ख्याल रखते हैं।
ये नियम बेस केस A (0, n), संरेखण (n + 3) और फज (-3) का ख्याल रखते हैं।


उदाहरण
उदाहरण
Line 378: 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 490: Line 496:
|}
|}
मिलान करने वाली समानताएं हैं  
मिलान करने वाली समानताएं हैं  
* जब टीआरएस कटौती नियम के साथ <math>\text{b6}</math> लागू की गई है:
*जब टीआरएस कटौती नियम के साथ <math>\text{b6}</math> लागू की गई है:
:<math>\begin{align}
:<math>\begin{align}
& A(2,1) +3
& A(2,1) +3
Line 508: 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 527: 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 567: 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''}}
Line 579: Line 585:
!3
!3
!4
!4
!''n''  
!''n''
|-
|-
!0
!0
|1
|1
|
|
2||3||4||5||<math>n + 1</math>
2||3||4|| 5||<math>n + 1</math>
|-
|-
!1
!1
|2
|2
|
|  
3||4||5||6||<math>n + 2 = 2 + (n + 3) - 3</math>
3|| 4|| 5||6||<math>n + 2 = 2 + (n + 3) - 3</math>
|-
|-
!2
! 2
|3
| 3
|
|
5||7||9||11||<math>2n + 3 = 2\cdot(n + 3) - 3</math>
5||7|| 9||11 ||<math>2n + 3 = 2\cdot(n + 3) - 3</math>
|-
|-
!3
!3
|5
| 5
|
|
13||29||61||125||<math>2^{(n + 3)} - 3</math>
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>
Line 633: Line 639:
|<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''}}
Line 648: Line 654:
!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
Line 665: Line 671:
|''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))
|}
|}
Line 676: Line 682:


===सामान्य टिप्पणी===
===सामान्य टिप्पणी===
* यह तुरंत स्पष्ट नहीं हो सकता है कि का मूल्यांकन <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 -->
*संगणनीयता सिद्धांत
*संगणनीयता सिद्धांत
Line 720: Line 726:
*[[गुडस्टीन समारोह|गुडस्टीन फलन]]
*[[गुडस्टीन समारोह|गुडस्टीन फलन]]
*मूल पुनरावर्ती फलन
*मूल पुनरावर्ती फलन
*[[रिकर्सन (कंप्यूटर विज्ञान)|पुनरावर्ती (कंप्यूटर विज्ञान)]]  
*[[रिकर्सन (कंप्यूटर विज्ञान)|पुनरावर्ती (कंप्यूटर विज्ञान)]]
<!-- keep alphabetical -->
<!-- keep alphabetical -->


Line 732: Line 738:




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




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


*संगणनीयता सिद्धांत
*संगणनीयता सिद्धांत
Line 1,044: Line 1,050:
*फलन रचना
*फलन रचना
*जोड़नेवाला
*जोड़नेवाला
*ढेर (सार डेटा प्रकार)
* स्टैक (सार डेटा प्रकार)
*अच्छी तरह से आदेश
*अच्छी तरह से आदेश
*लेक्सिकोग्राफिक ऑर्डर
*लेक्सिकोग्राफिक ऑर्डर
*घातांक प्रफलन
*घातांक प्रफलन
*तेजी से बढ़ने वाला पदानुक्रम
*तेजी से बढ़ने वाला पदानुक्रम
*उलटा काम करना
*प्रतिलोम काम करना
*न्यूनतम फैलाव वाला पेड़
*न्यूनतम फैलाव वाला पेड़
*असंयुक्त-सेट डेटा संरचना
*असंयुक्त-समूह डेटा संरचना
*फर्श फलन
*फर्श फलन
==बाहरी संबंध==
==बाहरी संबंध==
Line 1,071: Line 1,077:
{{Large numbers}}
{{Large numbers}}
{{Authority control}}
{{Authority control}}
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[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]
         
         
         
         
         
         
                   
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         

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

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