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

Revision as of 17:34, 18 December 2022

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

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

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

इतिहास

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

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

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

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

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

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

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

सामान्यीकृत अतिसंचालन, उदाहरण - $G(m,a,b)=a[m]b$ , एकरमैन फलन का भी एक संस्करण है।^[9] 1963 में आर.सी. बक अतिसंचालन सीक्वेंस पर एक सहज ज्ञान युक्त दो-चर ^{[n 1]}वेरिएंट $\operatorname {F}$ पर आधारित है:^[10]^[11]

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

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

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

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

परिभाषा

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

एकरमैन का मूल तीन-प्राचर फलन $\varphi (m,n,p)$ ऋणोतर पूर्णांकों के लिए निम्नानुसार पुनरावर्तन परिभाषित किया गया है $m,n,$ तथा $p$ :

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

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

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

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

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

या, नुथ के उच्च-तीर संकेतन में लिखा गया है (पूर्णांक सूचकांक में बढ़ाया गया

\geq -2

):

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

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

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

परिभाषा: पुनरावृत्त 1-सरणी फलन के रूप में परिभाषित करना

$f^{n}$ के n-वें पुनरावृति के रूप में $f$ :

{\begin{array}{rll}f^{0}(x)&=&x\\f^{n+1}(x)&=&f(f^{n}(x))\,\,\,\,\{{\textrm {for}}\,\,n\geq 1\}\end{array}}

पुनरावृत्त फलन एक निश्चित संख्या में स्वयं के साथ एक फलन बनाने की प्रक्रिया है। फलन रचना एक साहचर्य संक्रिया है, इसलिए $f(f^{n}(x))=f^{n}(f(x))$ .

एकरमैन फलन को एकल फलन के अनुक्रम के रूप में समझना, स्थित कर सकता है $\operatorname {A} _{m}(n)=\operatorname {A} (m,n)$ .

तब फलन एक एकल ^{[n 2]} फलन का अनुक्रम $\operatorname {A} _{0},\operatorname {A} _{1},\operatorname {A} _{2},...$ , जिसे हम पुनरावृत्त फलन से पारिभाषित कर सकते है :

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

संगणना

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

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

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

उदाहरण

गणना करना $A(1,2)\rightarrow _{*}4$ घटाव क्रम है ^{[n 3]}

Leftmost-outermost (one-step) strategy:	Leftmost-innermost (one-step) strategy:
${\underline {A(S(0),S(S(0)))}}$	${\underline {A(S(0),S(S(0)))}}$
$\rightarrow _{r3}{\underline {A(0,A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,{\underline {A(S(0),S(0))}})$
$\rightarrow _{r1}S({\underline {A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,A(0,{\underline {A(S(0),0)}}))$
$\rightarrow _{r3}S({\underline {A(0,A(S0,0))}})$	$\rightarrow _{r2}A(0,A(0,{\underline {A(0,S(0))}}))$
$\rightarrow _{r1}S(S({\underline {A(S(0),0)}}))$	$\rightarrow _{r1}A(0,{\underline {A(0,S(S(0)))}})$
$\rightarrow _{r2}S(S({\underline {A(0,S(0))}}))$	$\rightarrow _{r1}{\underline {A(0,S(S(S(0))))}}$
$\rightarrow _{r1}S(S(S(S(0))))$	$\rightarrow _{r1}S(S(S(S(0))))$

गणना करना $\operatorname {A} (m,n)$ कोई स्टैक (अमूर्त डेटा प्रकार) का उपयोग कर सकता है, जिसमें प्रारंभ में तत्व होते हैं $\langle m,n\rangle$ .

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

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

योजनाबद्ध रूप से, से शुरू $\langle m,n\rangle$ :

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

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

उदाहरण के लिए, आगम पर $\langle 2,1\rangle$ ,

the stack configurations	reflect the reduction^{[n 5]}
${\underline {2,1}}$	${\underline {A(2,1)}}$
$\rightarrow 1,{\underline {2,0}}$	$\rightarrow _{r1}A(1,{\underline {A(2,0)}})$
$\rightarrow 1,{\underline {1,1}}$	$\rightarrow _{r2}A(1,{\underline {A(1,1)}})$
$\rightarrow 1,0,{\underline {1,0}}$	$\rightarrow _{r3}A(1,A(0,{\underline {A(1,0)}}))$
$\rightarrow 1,0,{\underline {0,1}}$	$\rightarrow _{r2}A(1,A(0,{\underline {A(0,1)}}))$
$\rightarrow 1,{\underline {0,2}}$	$\rightarrow _{r1}A(1,{\underline {A(0,2)}})$
$\rightarrow {\underline {1,3}}$	$\rightarrow _{r1}{\underline {A(1,3)}}$
$\rightarrow 0,{\underline {1,2}}$	$\rightarrow _{r3}A(0,{\underline {A(1,2)}})$
$\rightarrow 0,0,{\underline {1,1}}$	$\rightarrow _{r3}A(0,A(0,{\underline {A(1,1)}}))$
$\rightarrow 0,0,0,{\underline {1,0}}$	$\rightarrow _{r3}A(0,A(0,A(0,{\underline {A(1,0)}})))$
$\rightarrow 0,0,0,{\underline {0,1}}$	$\rightarrow _{r2}A(0,A(0,A(0,{\underline {A(0,1)}})))$
$\rightarrow 0,0,{\underline {0,2}}$	$\rightarrow _{r1}A(0,A(0,{\underline {A(0,2)}}))$
$\rightarrow 0,{\underline {0,3}}$	$\rightarrow _{r1}A(0,{\underline {A(0,3)}})$
$\rightarrow {\underline {0,4}}$	$\rightarrow _{r1}{\underline {A(0,4)}}$
$\rightarrow 5$	$\rightarrow _{r1}5$

टिप्पणियां

रोसेटा कोड पर 225 कंप्यूटर भाषाओं में सबसे वामपंथी-अंतरतम रणनीति लागू की गई है।
सभी के लिए $m,n$ की गणना $A(m,n)$ से अधिक नहीं लेता है $(A(m,n)+1)^{m}$ कदम।^[17]
Grossman & Zeitman (1988) बताया कि की गणना में $\operatorname {A} (m,n)$ ढेर की अधिकतम लंबाई है $\operatorname {A} (m,n)$ , जब तक कि $m>0$ .

उनका अपना एल्गोरिदम, स्वाभाविक रूप से पुनरावृत्त, गणना करता है

\operatorname {A} (m,n)

अंदर

{\mathcal {O}}(m\operatorname {A} (m,n))

समय और भीतर

{\mathcal {O}}(m)

अंतरिक्ष।

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

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

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

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

पिछले खंड की तरह की गणना $\operatorname {A} _{m}^{1}(n)$ ढेर के साथ लागू किया जा सकता है।

प्रारंभ में ढेर में तीन तत्व होते हैं $\langle 1,m,n\rangle$ .

फिर बार-बार तीन शीर्ष तत्वों को नियमों के अनुसार बदल दिया जाता है^{[n 4]}: ${\begin{array}{lllllllll}{\text{(r4)}}&1&,0&,n&\rightarrow &(n+1)\\{\text{(r5)}}&1&,(m+1)&,n&\rightarrow &(n+1)&,m&,1\\{\text{(r6)}}&(x+2)&,m&,n&\rightarrow &1&,m&,(x+1)&,m&,n\\\end{array}}$ योजनाबद्ध रूप से, से शुरू $\langle 1,m,n\rangle$ :

जबकि ढेर की लंबाई <> 1
{
   पीओपी 3 तत्व;
   पुश 1 या 3 या 5 तत्व, नियमों को लागू करना r4, r5, r6;
}

उदाहरण

आगम पर $\langle 1,2,1\rangle$ क्रमिक ढेर विन्यास हैं

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

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

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

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

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

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

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

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

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

टिप्पणियां

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

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

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

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

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

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

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

{\begin{array}{lll}{\text{(b1)}}&F(S(0),0,n)&\rightarrow &S(n)\\{\text{(b2)}}&F(S(0),S(0),0)&\rightarrow &S(S(0))\\{\text{(b3)}}&F(S(0),S(S(0)),0)&\rightarrow &0\\{\text{(b4)}}&F(S(0),S(S(S(m))),0)&\rightarrow &S(0)\\{\text{(b5)}}&F(S(0),S(m),S(n))&\rightarrow &F(S(n),m,F(S(0),S(m),0))\\{\text{(b6)}}&F(S(S(x)),m,n)&\rightarrow &F(S(0),m,F(S(x),m,n))\end{array}}

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

{\begin{array}{lll}{\text{(b7)}}&F(S(S(x)),m,n)&\rightarrow &F(S(x),m,F(S(0),m,n))\end{array}}

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

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

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

उदाहरण

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

using reduction rule ${\text{b7}}$ :^{[n 5]}	using reduction rule ${\text{b6}}$ :^{[n 5]}
${\underline {A(2,1)}}$	${\underline {A(2,1)}}$
$\rightarrow _{r9}P({\underline {F(1,2,4)}})$	$\rightarrow _{r9}P({\underline {F(1,2,4)}})$
$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$	$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$
$\rightarrow _{b3}P({\underline {F(4,1,0)}})$	$\rightarrow _{b3}P({\underline {F(4,1,0)}})$
$\rightarrow _{b7}P(F(3,1,{\underline {F(1,1,0)}}))$	$\rightarrow _{b6}P(F(1,1,{\underline {F(3,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(3,1,2)}})$	$\rightarrow _{b6}P(F(1,1,F(1,1,{\underline {F(2,1,0)}})))$
$\rightarrow _{b7}P(F(2,1,{\underline {F(1,1,2)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,1,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b5}P(F(2,1,F(2,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(1,1,2)}})))$
$\rightarrow _{b2}P(F(2,1,{\underline {F(2,0,2)}}))$	$\rightarrow _{b5}P(F(1,1,F(1,1,F(2,0,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b7}P(F(2,1,F(1,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(2,0,2)}})))$
$\rightarrow _{b1}P(F(2,1,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,0,{\underline {F(1,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(2,1,4)}})$	$\rightarrow _{b1}P(F(1,1,F(1,1,{\underline {F(1,0,3)}})))$
$\rightarrow _{b7}P(F(1,1,{\underline {F(1,1,4)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,1,4)}}))$
$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$
$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$	$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$
$\rightarrow _{b7}P(F(1,1,F(3,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,{\underline {F(3,0,2)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(3,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,{\underline {F(2,0,2)}}))))$
$\rightarrow _{b7}P(F(1,1,F(2,0,{\underline {F(1,0,3)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}})))))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(2,0,4)}}))$	$\rightarrow _{b1}P(F(1,1,F(1,0,F(1,0,{\underline {F(1,0,3)}}))))$
$\rightarrow _{b7}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$	$\rightarrow _{b1}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$
$\rightarrow _{b1}P({\underline {F(1,1,6)}})$	$\rightarrow _{b1}P({\underline {F(1,1,6)}})$
$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$	$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(6,0,2)}})$	$\rightarrow _{b2}P({\underline {F(6,0,2)}})$
$\rightarrow _{b7}P(F(5,0,{\underline {F(1,0,2)}}))$	$\rightarrow _{b6}P(F(1,0,{\underline {F(5,0,2)}}))$
$\rightarrow _{b1}P({\underline {F(5,0,3)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,{\underline {F(4,0,2)}})))$
$\rightarrow _{b7}P(F(4,0,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,{\underline {F(3,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(4,0,4)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(2,0,2)}})))))$
$\rightarrow _{b7}P(F(3,0,{\underline {F(1,0,4)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}}))))))$
$\rightarrow _{b1}P({\underline {F(3,0,5)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,3)}})))))$
$\rightarrow _{b7}P(F(2,0,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,{\underline {F(1,0,4)}}))))$
$\rightarrow _{b1}P({\underline {F(2,0,6)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,{\underline {F(1,0,5)}})))$
$\rightarrow _{b7}P(F(1,0,{\underline {F(1,0,6)}}))$	$\rightarrow _{b1}P(F(1,0,{\underline {F(1,0,6)}}))$
$\rightarrow _{b1}P({\underline {F(1,0,7)}})$	$\rightarrow _{b1}P({\underline {F(1,0,7)}})$
$\rightarrow _{b1}{\underline {P(8)}}$	$\rightarrow _{b1}{\underline {P(8)}}$
$\rightarrow _{r10}5$	$\rightarrow _{r10}5$

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

जब टीआरएस कटौती नियम के साथ ${\text{b6}}$ लागू की गई है:

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

जब टीआरएस कटौती नियम के साथ ${\text{b7}}$ लागू की गई है:

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

टिप्पणियां

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

बड़ी संख्या

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

\begin{aligned} A (4, 3) & \to A (3, A (4, 2)) \\ \to A (3, A (3, A (4, 1))) \\ \to A (3, A (3, A (3, A (4, 0)))) \\ \to A (3, A (3, A (3, A (3, 1)))) \\ \to A (3, A (3, A (3, A (2, A (3, 0))))) \\ \to A (3, A (3, A (3, A (2, A (2, 1))))) \\ \to A (3, A (3, A (3, A (2, A (1, A (2, 0)))))) \end{aligned}

मानों की तालिका

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

Values of A(m, n)
n m	0	1	2	3	4	n
0	1	2\|\|3\|\|4\|\|5\|\| $n+1$
1	2	3\|\|4\|\| 5\|\| 6\|\| $n+2=2+(n+3)-3$
2	3	5\|\|7\|\|9\|\|11 \|\| $2n+3=2\cdot (n+3)-3$
3	5	13\|\|29\|\| 61\|\|125\|\| $2^{(n+3)}-3$
4	13 $={2^{2^{2}}}-3$ $=2\uparrow \uparrow 3-3$	65533 $={2^{2^{2^{2}}}}-3$ $=2\uparrow \uparrow 4-3$	2⁶⁵⁵³⁶ − 3 $={2^{2^{2^{2^{2}}}}}-3$ $=2\uparrow \uparrow 5-3$	${2^{2^{65536}}}-3$ $={2^{2^{2^{2^{2^{2}}}}}}-3$ $=2\uparrow \uparrow 6-3$	${2^{2^{2^{65536}}}}-3$ $={2^{2^{2^{2^{2^{2^{2}}}}}}}-3$ $=2\uparrow \uparrow 7-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} _{n+3}-3\end{matrix}}$ $=2\uparrow \uparrow (n+3)-3$
5	65533 $=2\uparrow \uparrow (2\uparrow \uparrow 2)-3$ $=2\uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow (n+3)-3$
6	$2\uparrow \uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow \uparrow (n+3)-3$
m	$(2\to 3\to (m-2))-3$	$(2\to 4\to (m-2))-3$	$(2\to 5\to (m-2))-3$	$(2\to 6\to (m-2))-3$	$(2\to 7\to (m-2))-3$	$(2\to (n+3)\to (m-2))-3$

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

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

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

Values of A(m, n)
n m	0	1	2	3	4	n
0	0+1	1+1	2+1	3+1	4+1	n + 1
1	A(0, 1)	A(0, A(1, 0)) = A(0, 2)	A(0, A(1, 1)) = A(0, 3)	A(0, A(1, 2)) = A(0, 4)	A(0, A(1, 3)) = A(0, 5)	A(0, A(1, n−1))
2	A(1, 1)	A(1, A(2, 0)) = A(1, 3)	A(1, A(2, 1)) = A(1, 5)	A(1, A(2, 2)) = A(1, 7)	A(1, A(2, 3)) = A(1, 9)	A(1, A(2, n−1))
3	A(2, 1)	A(2, A(3, 0)) = A(2, 5)	A(2, A(3, 1)) = A(2, 13)	A(2, A(3, 2)) = A(2, 29)	A(2, A(3, 3)) = A(2, 61)	A(2, A(3, n−1))
4	A(3, 1)	A(3, A(4, 0)) = A(3, 13)	A(3, A(4, 1)) = A(3, 65533)	A(3, A(4, 2))	A(3, A(4, 3))	A(3, A(4, n−1))
5	A(4, 1)	A(4, A(5, 0))	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))	A(4, A(5, n−1))
6	A(5, 1)	A(5, A(6, 0))	A(5, A(6, 1))	A(5, A(6, 2))	A(5, A(6, 3))	A(5, A(6, n−1))

गुण

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

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

=== मूल पुनरावर्ती === नहीं

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

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

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

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

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

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

उलटा

फलन के बाद से f(n) = A(n, n) ऊपर माना गया बहुत तेजी से बढ़ता है, इसका उलटा फलन, f⁻¹, बहुत धीमी गति से बढ़ता है। यह व्युत्क्रम एकरमैन फलन f⁻¹ को आमतौर पर α से दर्शाया जाता है। वास्तव में, α(n) किसी भी व्यावहारिक आगम आकार n के लिए 5 से कम है, क्योंकि A(4, 4) के आदेश पर है $2^{2^{2^{2^{16}}}}$ .

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

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

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

यह फलन ऊपर उल्लिखित एल्गोरिदम के अधिक सटीक विश्लेषण में उत्पन्न होता है, और अधिक परिष्कृत समय सीमा प्रदान करता है। असम्बद्ध-सेट डेटा संरचना में, एम संचालन की संख्या का प्रतिनिधित्व करता है जबकि एन तत्वों की संख्या का प्रतिनिधित्व करता है; मिनिमम स्पैनिंग ट्री एल्गोरिथम में, m किनारों की संख्या का प्रतिनिधित्व करता है जबकि n वर्टिकल की संख्या का प्रतिनिधित्व करता है। की कई थोड़ी अलग परिभाषाएँ α(m, n) मौजूद; उदाहरण के लिए, log₂ n कभी-कभी n द्वारा प्रतिस्थापित किया जाता है, और कभी-कभी फर्श फलन को छत फलन द्वारा प्रतिस्थापित किया जाता है।

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

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

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

यह भी देखें

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

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

संदर्भ

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

ग्रन्थसूची

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

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

संगणनीयता सिद्धांत
पूर्ण फलन
सूडान फलन
योग
प्रत्यावर्तन
पुनरावृत्त फलन
फलन रचना
जोड़नेवाला
ढेर (सार डेटा प्रकार)
अच्छी तरह से आदेश
लेक्सिकोग्राफिक ऑर्डर
घातांक प्रफलन
तेजी से बढ़ने वाला पदानुक्रम
उलटा काम करना
न्यूनतम फैलाव वाला पेड़
असंयुक्त-सेट डेटा संरचना
फर्श फलन

बाहरी संबंध

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

[letop3-10] with parameter order reversed

[letop4-16] 'curried'

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

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

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

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

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

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

[FOOTNOTEAckermann1928-2] 2.0 ^2.1 Ackermann 1928.

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

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

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

[FOOTNOTEvan_Heijenoort1977-6] van Heijenoort 1977.

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

[FOOTNOTERobinson1948-8] Robinson 1948.

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

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

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

[FOOTNOTEMunafo1999a-13] Munafo 1999a.

[FOOTNOTESundblad1971-14] 13.0 ^13.1 Sundblad 1971.

[FOOTNOTEPortoMatos1980-15] Porto & Matos 1980.

[FOOTNOTEGrossmanZeitman1988-17] Grossman & Zeitman 1988.

[FOOTNOTEPaulson2021-18] Paulson 2021.

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

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

[FOOTNOTEPettie2002-26] Pettie 2002.

[FOOTNOTEMatos2014-27] Matos 2014.

[FOOTNOTEVaida1970-28] Vaida 1970.

[FOOTNOTEWichmann1976-29] Wichmann 1976.

[FOOTNOTEWichmann1977-30] Wichmann 1977.

[FOOTNOTEWichmann1982-31] Wichmann 1982.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[n 1]

[10]

[11]

[12]

[13]

[14]

[n 2]

[15]

[16]

[n 3]

[n 4]

[n 5]

[17]

[n 6]

[n 7]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

@@ Line 59: / Line 59: @@
 \varphi(m, n, p) &= \varphi(m, \varphi(m, n-1, p), p - 1) && \text{for } n, p > 0
 \end{align}</math>
-विभिन्न दो-प्राचर संस्करणों में से, पेटर और रॉबिन्सन द्वारा विकसित एक (जिसे अधिकांश लेखकों द्वारा एकरमैन फलन कहा जाता है) को ऋणोतर पूर्णांकों के लिए परिभाषित किया गया है <math>m</math> तथा <math>n</math> निम्नलिखित नुसार:
+विभिन्न दो-प्राचर संस्करणों में से, पेटर और रॉबिन्सन द्वारा विकसित एक (जिसे अधिकांश लेखकों द्वारा एकरमैन फलन कहा जाता है) को ऋणोतर पूर्णांकों  <math>m</math> तथा <math>n</math> के लिए निम्नलिखित अनुसार परिभाषित किया गया है :
 :<math>
@@ Line 68: / Line 68: @@
 \end{array}
 </math>
-अतिसंचालन के संबंध में एकरमेन फलन भी व्यक्त किया गया है:{{sfn|Sundblad|1971}}{{sfn|Porto|Matos|1980}}
+एकरमेन फलन को अतिसंचालन अनुक्रम के संबंध में भी व्यक्त किया गया है:{{sfn|Sundblad|1971}}{{sfn|Porto|Matos|1980}}
 :<math>A(m,n) = \begin{cases}
   n+1 & m=0 \\
 [m](n+3)-3 & m>0 \\
 \end{cases}</math>
-:या, नुथ के उच्च-तीर संकेतन में लिखा गया है (पूर्णांक सूचकांकों तक विस्तारित <math>\geq -2</math>):
+:या, नुथ के उच्च-तीर संकेतन में लिखा गया है (पूर्णांक सूचकांक में बढ़ाया गया <math>\geq -2</math>):
 ::: <math> = \begin{cases}
   n+1 & m=0 \\
 \uparrow^{m-2} (n+3) - 3 & m>0 \\
   \end{cases}</math>
-:या, समतुल्य रूप से, बक के फलन F के संदर्भ में:{{sfn|Buck|1963}} :::<math> = \begin{cases}
+:या, समतुल्य रूप से, बक के फलन F के संदर्भ में:{{sfn|Buck|1963}}
+:<math> = \begin{cases}
   n+1 & m=0 \\
   F(m,n+3) - 3 & m>0 \\
 \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}
 f^{0}(x) & = & x \\
 f^{n+1}(x) & = & f(f^{n}(x))\,\,\,\, \{\textrm{for} \,\, n \geq 1\}
 \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>
 \begin{array}{lcl}
@@ Line 678: / Line 678: @@
 *यह तुरंत स्पष्ट नहीं हो सकता है कि का मूल्यांकन <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 का जोड़ है। इसकी तेजी से बढ़ती शक्ति पूरी तरह से नेस्टेड पुनरावर्तन पर आधारित है। इसका तात्पर्य यह भी है कि इसके चलने का समय कम से कम इसके उत्पादन के अनुपात में है, और यह भी बहुत बड़ा है। वास्तविकता में, ज्यादातर मामलों में चलने का समय आउटपुट से कहीं बड़ा होता है; ऊपर देखो।
+*एक दिलचस्प पहलू यह है कि इसके द्वारा उपयोग किया जाने वाला एकमात्र अंकगणितीय संक्रिया 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> जो स्पष्ट रूप से [[ट्यूरिंग मशीन]] जैसी अनंत मेमोरी वाली मशीन पर गणना योग्य है और इसलिए एक गणना योग्य फलन है, किसी भी मूल पुनरावर्ती फलन की तुलना में तेजी से बढ़ता है और इसलिए मूल पुनरावर्ती नहीं है।

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

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 17:34, 18 December 2022

Contents

इतिहास

परिभाषा

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

परिभाषा: पुनरावृत्त 1-सरणी फलन के रूप में परिभाषित करना

संगणना

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

बड़ी संख्या

मानों की तालिका

गुण

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

उलटा

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

यह भी देखें

टिप्पणियाँ

संदर्भ

ग्रन्थसूची

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

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 17:34, 18 December 2022

इतिहास

परिभाषा

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

परिभाषा: पुनरावृत्त 1-सरणी फलन के रूप में परिभाषित करना

संगणना

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

बड़ी संख्या

मानों की तालिका

गुण

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

उलटा

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

यह भी देखें

टिप्पणियाँ

संदर्भ

ग्रन्थसूची

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

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories