मौलिक पुनरावर्ती फलन: Difference between revisions

Revision as of 02:04, 9 February 2023

कम्प्यूटेबिलिटी सिद्धांत में, प्राचीन पुनरावर्ती कार्य, मोटे तौर पर बोलना, एक ऐसा कार्य है जिसकी गणना एक कंप्यूटर प्रोग्राम द्वारा की जा सकती है, जिसके लूप सभी "फॉर" लूप हैं लूप के लिए (अर्थात, प्रत्येक लूप के पुनरावृत्तियों की संख्या की ऊपरी सीमा पहले निर्धारित की जा सकती है) प्राचीन पुनरावर्ती कार्य उन सामान्य पुनरावर्ती कार्यो का एक सख्त उपसमुच्चय बनाते हैं जो कुल कार्य भी हैं।

प्राचीन पुनरावर्ती कार्यों का महत्व इस तथ्य में निहित है कि संख्या सिद्धांत (और सामान्यतः गणित में) में अध्ययन किए जाने वाले अधिकांश संगणनीय कार्य प्राचीन पुनरावर्ती हैं। उदाहरण के लिए, योग और विभाजन, क्रमगुणित और चरघातांकी फलन, और जो फलन n अभाज्य को लौटाता है, सभी प्राचीन पुनरावर्ती हैं। ^[1] वास्तव में, यह दिखाने के लिए कि एक संगणनीय कार्य प्राचीन पुनरावर्ती है, यह दिखाने के लिए पर्याप्त है कि इसकी समय जटिलता इनपुट आकार के एक प्राचीन पुनरावर्ती कार्य से ऊपर है।^{[citation needed]} इसलिए एक संगणनीय कार्य को तैयार करना इतना आसान नहीं है कि प्राचीन पुनरावर्ती नहीं है; कुछ उदाहरण नीचे अनुभाग § सीमाएँ में दिखाए गए हैं।

कम्प्यूटेशनल जटिलता सिद्धांत में प्राचीन पुनरावर्ती कार्यों के सेट को पीआर के रूप में जाना जाता है।

परिभाषा

एक प्राचीन पुनरावर्ती फ़ंक्शन तर्कों की एक निश्चित संख्या लेता है, प्रत्येक एक प्राकृतिक संख्या (गैर-नकारात्मक पूर्णांक: {0, 1, 2, ...}), और एक प्राकृतिक संख्या देता है। यदि यह n तर्क लेता है तो इसे n-ary कहा जाता है।

बुनियादी प्राचीन पुनरावर्ती कार्य इन स्वयंसिद्धों द्वारा दिए गए हैं:

'लगातार कार्य Ck n: प्रत्येक प्राकृतिक संख्या के लिए $n$ और हर $k$ ,के लिए k-ary नियतांक फलन, द्वारा परिभाषित $C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n$ , प्राचीन पुनरावर्ती है।
उत्तराधिकारी फलन: 1-ऐरी उत्तरवर्ती फलन S, जो अपने तर्क का परवर्ती लौटाता है (पीनो अभिधारणाएं देखें), अर्थात्, $S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1$ , प्राचीन पुनरावर्ती है।
प्रोजेक्शन फंक्शन $P_{i}^{k}$ : सभी प्राकृतिक संख्याओं के लिए $i,k$ ऐसा है कि $1\leq i\leq k$ , k-ary फ़ंक्शन द्वारा परिभाषित $P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}$ प्राचीन पुनरावर्ती है।

इन स्वयंसिद्धों द्वारा दिए गए कार्यों को लागू करके अधिक जटिल प्राचीन पुनरावर्ती कार्य प्राप्त किए जा सकते हैं:

फ़ंक्शन f 0 से इसके पहले तर्क के मान तक फॉर-लूप के रूप में कार्य करता है। f के लिए बाकी तर्क, यहाँ x से दर्शाए गए हैं₁, ..., एक्स_k, फॉर-लूप के साथ निरूपित, फॉर-लूप के लिए प्रारंभिक शर्तों का एक सेट है, जिसका उपयोग इसके द्वारा गणना के दौरान किया जा सकता है, लेकिन जो इसके द्वारा अपरिवर्तनीय हैं। फ़ंक्शन g और h समीकरणों के दाईं ओर जो f को परिभाषित करते हैं, लूप के शरीर का प्रतिनिधित्व करते हैं, जो गणना करता है। प्रारंभिक गणना करने के लिए फ़ंक्शन g का उपयोग केवल एक बार किया जाता है। लूप के बाद के चरणों की गणना एच द्वारा की जाती है। एच के पहले पैरामीटर को फॉर-लूप के इंडेक्स का "वर्तमान" मान खिलाया जाता है। एच का दूसरा पैरामीटर पिछले चरणों से फॉर-लूप की पिछली गणनाओं का परिणाम है। एच के लिए बाकी पैरामीटर पहले बताए गए फॉर-लूप के लिए अपरिवर्तनीय प्रारंभिक शर्तें हैं। उनका उपयोग h द्वारा गणना करने के लिए किया जा सकता है लेकिन वे स्वयं h द्वारा परिवर्तित नहीं होंगे।
मौलिक पुनरावर्ती फलन $ρ$ : K-ary फलन दिया गया है $g(x_{1},\ldots ,x_{k})\,$ और (k + 2)-एरी फ़ंक्शन $h(y,z,x_{1},\ldots ,x_{k})\,$ : ${\begin{aligned}\rho (g,h)&\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where the }}(k+1){\text{-ary function }}f{\text{ is defined by}}\\f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k})\\f(S(y),x_{1},\ldots ,x_{k})&=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}$
व्याख्या:
फंक्शन f फॉर-लूप के रूप में 0 से इसके पहले तर्क के मान तक कार्य करता है। f के लिए बाकी तर्क, यहां x₁, ..., x_{k' से दर्शाए गए हैं '}, फॉर-लूप के लिए प्रारंभिक शर्तों का एक सेट है जो गणना के दौरान इसके द्वारा उपयोग किया जा सकता है लेकिन जो इसके द्वारा अपरिवर्तनीय हैं। फ़ंक्शन g और h समीकरणों के दाईं ओर जो f को परिभाषित करते हैं, लूप के शरीर का प्रतिनिधित्व करते हैं, जो गणना करता है। फ़ंक्शन g का उपयोग प्रारंभिक गणना करने के लिए केवल एक बार किया जाता है। लूप के बाद के चरणों की गणना h द्वारा की जाती है। h का पहला पैरामीटर फॉर-लूप के इंडेक्स के "वर्तमान" मान को फीड किया जाता है। h का दूसरा पैरामीटर पिछले चरणों से, फॉर-लूप की पिछली गणनाओं का परिणाम है। h के लिए बाकी पैरामीटर पहले बताए गए फॉर-लूप के लिए अपरिवर्तनीय प्रारंभिक शर्तें हैं। उनका उपयोग h द्वारा गणना करने के लिए किया जा सकता है लेकिन वे स्वयं h द्वारा परिवर्तित नहीं होंगे।

'प्राचीन पुनरावर्ती कार्य' मूल कार्य हैं और इन कार्यों को सीमित संख्या में लागू करके मूल कार्यों से प्राप्त किए जाते हैं।

उदाहरण

$C_{0}^{1}$ एक 1-एरी फ़ंक्शन है जो रिटर्न देता है $0$ प्रत्येक इनपुट के लिए: $C_{0}^{1}(x)=0$ .
$C_{1}^{1}$ एक 1-एरी फ़ंक्शन है जो रिटर्न देता है 1 प्रत्येक इनपुट के लिए :Failed to parse (⧼math_empty_tex⧽): {\displaystyle } $C_{1}^{1}(x)=1$ .
$C_{3}^{0}$ एक 0-एरी फ़ंक्शन है, यानी स्थिर: $C_{3}^{0}=3$ .
$P_{1}^{1}$ प्राकृतिक संख्याओं पर पहचान कार्य है:: $P_{1}^{1}(x)=x$ .
$P_{1}^{2}$ and $P_{2}^{2}$ प्राकृतिक संख्या युग्मों पर क्रमशः बाएँ और दाएँ प्रक्षेपण है: $P_{1}^{2}(x,y)=x$ and $P_{2}^{2}(x,y)=y$ .
$S\circ S$ एक 1-एरी फ़ंक्शन है जो इसके इनपुट में 2 जोड़ता है, $(S\circ S)(x)=x+2$ .
$S\circ C_{0}^{1}$ एक 1-एरी फ़ंक्शन है जो प्रत्येक इनपुट के लिए 1 लौटाता है: $(S\circ C_{0}^{1})(x)=S(C_{0}^{1}(x))=S(0)=1$ . That is, $S\circ C_{0}^{1}$ और $C_{1}^{1}$ एक ही कार्य हैं: $S\circ C_{0}^{1}=C_{1}^{1}$ . इसी तरह, हर $C_{n}^{1}$ उचित रूप से कई की रचना के रूप में व्यक्त किया जा सकता है $S$ और $C_{0}^{1}$ .

जोड़

2-एरी फ़ंक्शन की परिभाषा $Add$ , इसके तर्कों के योग की गणना करने के लिए, प्रिमिटिव रिकर्सन ऑपरेटर का उपयोग करके प्राप्त किया जा सकता है $\rho$ . इसके लिए, प्रसिद्ध समीकरण

{\begin{array}{rcll}0+y&=&y&{\text{ and}}\\S(x)+y&=&S(x+y)&.\\\end{array}}

"प्राचीन पुनरावर्ती कार्य शब्दावली में पुनर्प्रकाशित" हैं: की परिभाषा में $\rho (g,h)$ , पहला समीकरण चुनने का सुझाव देता है $g=P_{1}^{1}$ प्राप्त करने के लिए $Add(0,y)=g(y)=y$ ; दूसरा समीकरण चुनने का सुझाव देता है $h=S\circ P_{2}^{3}$ प्राप्त करने के लिए $Add(S(x),y)=h(x,Add(x,y),y)=(S\circ P_{2}^{3})(x,Add(x,y),y)=S(Add(x,y))$ . इसलिए, अतिरिक्त फ़ंक्शन को इस रूप में परिभाषित किया जा सकता है $Add=\rho (P_{1}^{1},S\circ P_{2}^{3})$ . गणना उदाहरण के रूप में,

{\begin{array}{lll}&Add(1,7)\\=&\rho (P_{1}^{1},S\circ P_{2}^{3})\;(S(0),7)&{\text{ by Def. }}Add,S\\=&(S\circ P_{2}^{3})(0,Add(0,7),7)&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&S(Add(0,7))&{\text{ by Def. }}\circ ,P_{2}^{3}\\=&S(\;\rho (P_{1}^{1},S\circ P_{2}^{3})\;(0,7)\;)&{\text{ by Def. }}Add\\=&S(P_{1}^{1}(7))&{\text{ by case }}\rho (g,h)\;(0,...)\\=&S(7)&{\text{ by Def. }}P_{1}^{1}\\=&8&{\text{ by Def. }}S.\\\end{array}}

दोहरीकरण

दिया गया $Add$ , 1-एरी फ़ंक्शन $Add\circ (P_{1}^{1},P_{1}^{1})$ इसके तर्क को दोगुना करता है, $(Add\circ (P_{1}^{1},P_{1}^{1}))(x)=Add(x,x)=x+x$ .

गुणन

योग की तरह, गुणन को किसके द्वारा परिभाषित किया जा सकता है $Mul=\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))$ . यह प्रसिद्ध गुणा समीकरणों को पुन: उत्पन्न करता है:

{\begin{array}{lll}&Mul(0,y)\\=&\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))\;(0,y)&{\text{ by Def. }}Mul\\=&C_{0}^{1}(y)&{\text{ by case }}\rho (g,h)\;(0,...)\\=&0&{\text{ by Def. }}C_{0}^{1}.\\\end{array}}

और

{\begin{array}{lll}&Mul(S(x),y)\\=&\rho (C_{0}^{1},Add\circ (P_{2}^{3},P_{3}^{3}))\;(S(x),y)&{\text{ by Def. }}Mul\\=&(Add\circ (P_{2}^{3},P_{3}^{3}))\;(x,Mul(x,y),y)&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&Add(Mul(x,y),y)&{\text{ by Def. }}\circ ,P_{2}^{3},P_{3}^{3}\\=&Mul(x,y)+y&{\text{ by property of }}Add.\\\end{array}}

पूर्ववर्ती

पूर्ववर्ती कार्य उत्तराधिकारी कार्य के विपरीत कार्य करता है और नियमों द्वारा पुनरावर्ती रूप से परिभाषित किया जाता है $Pred(0)=0$ और $Pred(S(n))=n$ . एक प्राचीन पुनरावर्ती परिभाषा है $Pred=\rho (C_{0}^{0},P_{1}^{2})$ . गणना उदाहरण के रूप में,

{\begin{array}{lll}&Pred(8)\\=&\rho (C_{0}^{0},P_{1}^{2})\;(S(7))&{\text{ by Def. }}Pred,S\\=&P_{1}^{2}(7,Pred(7))&{\text{ by case }}\rho (g,h)\;(S(...),...)\\=&7&{\text{ by Def. }}P_{1}^{2}.\\\end{array}}

कटा हुआ घटाव

सीमित घटाव फ़ंक्शन (जिसे monus भी कहा जाता है, और निरूपित किया जाता है ${\stackrel {.}{-}}$ ) पूर्ववर्ती कार्य से निश्चित है। यह समीकरणों को संतुष्ट करता है

{\begin{array}{rcll}y{\stackrel {.}{-}}0&=&y&{\text{and}}\\y{\stackrel {.}{-}}S(x)&=&Pred(y{\stackrel {.}{-}}x)&.\\\end{array}}

चूंकि पुनरावर्तन दूसरे तर्क पर चलता है, हम उलटे घटाव की एक प्राचीन पुनरावर्ती परिभाषा के साथ प्रारंभ करते हैं, $RSub(y,x)=x{\stackrel {.}{-}}y$ . इसका पुनरावर्तन तब पहले तर्क पर चलता है, इसलिए इसकी प्राचीन पुनरावर्ती परिभाषा प्राप्त की जा सकती है, इसके अतिरिक्त, जैसा $RSub=\rho (P_{1}^{1},Pred\circ P_{2}^{3})$ . उल्टे तर्क क्रम से छुटकारा पाने के लिए, फिर परिभाषित करें $Sub=RSub\circ (P_{2}^{2},P_{1}^{2})$ . गणना उदाहरण के रूप में,

\begin{array}{lll} S u b (8, 1) \\ = & (R S u b \circ (P_{2}^{2}, P_{1}^{2})) (8, 1) & by Def. S u b \\ = & R S u b (1, 8) & by Def. \circ, P_{2}^{2}, P_{1}^{2} \\ = & ρ (P_{1}^{1}, P r e d \circ P_{2}^{3}) (S (0), 8) & by Def. R S u b, S \\ = & (P r e d \circ P_{2}^{3}) (0, R S u b (0, 8), 8) & by case ρ (g, h) (S (. . .), . . .) \\ = & P r e d (R S u b (0, 8)) & by Def. \circ, P_{2}^{3} \\ = & P r e d (ρ (P_{1}^{1}, \end{array}

विधेय को संख्यात्मक कार्यों में परिवर्तित करना

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

IsZero

इस प्रकार परिभाषित किया जाएगा

IsZero(x)=1

यदि

x=0

, और

$IsZero(x)=0$ , अन्यथा। इसे परिभाषित करके प्राप्त किया जा सकता है $IsZero=\rho (C_{1}^{0},C_{0}^{2})$ . तब, $IsZero(0)=\rho (C_{1}^{0},C_{0}^{2})(0)=C_{1}^{0}(0)=1$ और उदा. $IsZero(8)=\rho (C_{1}^{0},C_{0}^{2})(S(7))=C_{0}^{2}(7,IsZero(7))=0$ .

विधेय कम या बराबर

संपत्ति का उपयोग करना $x\leq y\iff x{\stackrel {.}{-}}y=0$ , 2-एरी फ़ंक्शन $Leq$ द्वारा परिभाषित किया जा सकता है $Leq=IsZero\circ Sub$ . तब $Leq(x,y)=1$ यदि $x\leq y$ , और $Leq(x,y)=0$ , अन्यथा। गणना उदाहरण के रूप में,

{\begin{array}{lll}&Leq(8,3)\\=&IsZero(Sub(8,3))&{\text{ by Def. }}Leq\\=&IsZero(5)&{\text{ by property of }}Sub\\=&0&{\text{ by property of }}IsZero\\\end{array}}

विधेय ग्रेटर या बराबर

एक बार की परिभाषा $Leq$ प्राप्त होता है, तो विलोम विधेय को इस प्रकार परिभाषित किया जा सकता है $Geq=Leq\circ (P_{2}^{2},P_{1}^{2})$ . तब, $Geq(x,y)=Leq(y,x)$ सत्य है (अधिक त्रुटिहीन: मान 1 है) यदि, और केवल यदि, $x\geq y$ .

यदि-तो-और

प्रोग्रामिंग भाषाओं से ज्ञात 3-एरी if-then-else ऑपरेटर द्वारा परिभाषित किया जा सकता है ${\textit {If}}=\rho (P_{2}^{2},P_{3}^{4})$ . फिर, मनमानी के लिए $x$ ,

{\begin{array}{lll}&{\textit {If}}(S(x),y,z)\\=&\rho (P_{2}^{2},P_{3}^{4})\;(S(x),y,z)&{\text{ by Def. }}{\textit {If}}\\=&P_{3}^{4}(x,{\textit {If}}(x,y,z),y,z)&{\text{ by case }}\rho (S(...),...)\\=&y&{\text{ by Def. }}P_{3}^{4}\\\end{array}}

और

{\begin{array}{lll}&{\textit {If}}(0,y,z)\\=&\rho (P_{2}^{2},P_{3}^{4})\;(0,y,z)&{\text{ by Def. }}{\textit {If}}\\=&P_{2}^{2}(y,z)&{\text{ by case }}\rho (0,...)\\=&z&{\text{ by Def. }}P_{2}^{2}.\\\end{array}}

.

वह है, ${\textit {If}}(x,y,z)$ तत्कालीन भाग देता है, $y$ , यदि-भाग, $x$ , सत्य है, और अन्य भाग, $z$ , अन्यथा।

जंक्शन

पर आधारित ${\textit {If}}$ कार्य, तार्किक जंक्शनों को परिभाषित करना आसान है। उदाहरण के लिए परिभाषित करना $And={\textit {If}}\circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})$ , एक प्राप्त करता है $And(x,y)={\textit {If}}(x,y,0)$ , वह है, $And(x,y)$ सच है यदि, और केवल यदि, दोनों $x$ और $y$ सत्य हैं (तार्किक संयोजन $x$ और $y$ ).

इसी प्रकार, $Or={\textit {If}}\circ (P_{1}^{2},C_{1}^{2},P_{2}^{2})$ और $Not={\textit {If}}\circ (P_{1}^{1},C_{0}^{1},C_{1}^{1})$ वियोजन और निषेध की उपयुक्त परिभाषाओं की ओर ले जाते हैं: $Or(x,y)={\textit {If}}(x,1,y)$ और $Not(x)={\textit {If}}(x,0,1)$ .

समानता विधेय

उपरोक्त कार्यों का उपयोग करना $Leq$ , $Geq$ और $And$ , मानहानि $Eq=And\circ (Leq,Geq)$ समानता विधेय को लागू करता है। वास्तव में, $Eq(x,y)=And(Leq(x,y),Geq(x,y))$ सच है यदि, और केवल यदि, $x$ के बराबर होती है $y$ .

इसी प्रकार, परिभाषा $Lt=Not\circ Geq$ कम-से-कम विधेय को लागू करता है, और $Gt=Not\circ Leq$ से अधिक लागू करता है।

प्राकृत संख्याओं पर अन्य संक्रियाएं

घातांक और प्रारंभिक परीक्षण प्राचीन पुनरावर्ती हैं। प्राचीन पुनरावर्ती कार्यों e, f, g, और h को देखते हुए, एक फ़ंक्शन जो e≤f होने पर g का मान लौटाता है और अन्यथा h का मान प्राचीन पुनरावर्ती होता है।

पूर्णांकों और परिमेय संख्याओं पर संक्रियाएं

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

कुछ सामान्य प्राचीन पुनरावर्ती कार्य

निम्नलिखित उदाहरण और परिभाषाएँ क्लेन (1952) पीपी. 223–231 से हैं - कई सबूतों के साथ दिखाई देते हैं। बूलोस-बर्गेस-जेफरी 2002 पीपी। 63-70 में अधिकांश समान नामों के साथ, या तो प्रमाण के रूप में या उदाहरण के रूप में दिखाई देते हैं; वे त्रुटिहीन व्युत्पत्ति के आधार पर लघुगणक lo(x, y) या lg(x, y) जोड़ते हैं।

निम्नलिखित में हम देखते हैं कि आदिम पुनरावर्ती कार्य चार प्रकार के हो सकते हैं:

संक्षेप में कार्य: "संख्या-सैद्धांतिक कार्य" {0, 1, 2, ...} से {0, 1, 2, ...} तक,
विधेय: {0, 1, 2, ...} से सत्य मान {t =सत्य, f =असत्य},
तर्कवाक्य संयोजक: सत्य मान {t, f} से सत्य मान {t, f},
कार्यों का प्रतिनिधित्व: सत्य मान {टी, एफ} से {0, 1, 2, ...}। कई बार एक विधेय को विधेय के आउटपुट { t, f } को { 0, 1 } में परिवर्तित करने के लिए एक प्रतिनिधित्व समारोह की आवश्यकता होती है (~sg() परिभाषित के साथ "t" से "0" और "f" से "1" के क्रम पर ध्यान दें नीचे)। परिभाषा के अनुसार एक फ़ंक्शन φ(x) विधेय P(x) का एक "प्रतिनिधित्व फ़ंक्शन" है यदि φ केवल मान 0 और 1 लेता है और 0 उत्पन्न करता है जब P सत्य है"।

निम्नलिखित में चिह्न " ' ", उदा. a' आदिम चिह्न है जिसका अर्थ है "का उत्तराधिकारी", सामान्यतः " +1", के रूप में माना जाता है, उदा a +1 = डीईएफ़ a'। कार्यों 16-20 और #G आदिम पुनरावर्ती विधेय को परिवर्तित करने और उन्हें निकालने के संबंध में विशेष रुचि रखते हैं, उनके "अंकगणितीय" रूप को गोडेल संख्या के रूप में व्यक्त किया गया है।

जोड़: a+b
गुणन: a×b

घातांक: a^b

क्रमगुणित ए! :0! = 1, a'! = a!×a'
पूर्ववर्ती (ए): (पूर्ववर्ती या कमी): यदि a > 0 तो a-1 और 0
उचित घटाव a ∸ b: यदि a ≥ b तो a-b और 0
न्यूनतम (a₁, ... a_n)
अधिकतम (a₁, ... a_n)
पूर्ण अंतर: | a-b | =_def (a ∸ b) + (b ∸ a)
~sg(a): NOT[signum(a)]: यदि a=0 तो 1 और 0

sg(a): signum a: यदि a=0 तो 0 और 1

a | b: (a b को विभाजित करता है): यदि b=k×a कुछ k के लिए तो 0 और 1
शेष (a, b): बचे हुए यदि बी "समान रूप से" विभाजित नहीं करता है। एमओडी (a, b) भी कहा जाता है
a = b: sg | a - b | (क्लीन की प्रथा 0 से सत्य और 1 से असत्य का प्रतिनिधित्व करना था; वर्तमान में, विशेष रूप से कंप्यूटर में, सबसे आम सम्मेलन रिवर्स है, अर्थात् 1 से सत्य और 0 से गलत का प्रतिनिधित्व करने के लिए, जो यहाँ और sg में ~sg को बदलने की मात्रा है। अगला आइटम)
a < b:: sg( a' ∸ b)
Pr(a): a एक अभाज्य संख्या है Pr(a) =_def a>1 & NOT(उपस्थित c)_1<c<a [ c|a ]
p_i: i+1-st अभाज्य संख्या
(a)_i: a में pi का प्रतिपादक: अद्वितीय x ऐसा है कि p_i^x|a & NOT(p_i^x'|a)
lh(a): "लंबाई" या गैर-लुप्त होने वाले एक्सपोनेंट्स की संख्या
lo(a, b): (आधार b का लघुगणक): यदि a, b > 1 तो सबसे बड़ा x ऐसा है कि b^x | a अन्य 0

निम्नलिखित में संक्षिप्त रूप 'x' =_def एक्स₁, ... एक्स_n; अर्थ की आवश्यकता होने पर सबस्क्रिप्ट लागू किया जा सकता है।

#A: एक फ़ंक्शन φ स्पष्ट रूप से फ़ंक्शन Ψ और स्थिरांक q से निश्चित है q₁, ... q_n Ψ में प्राचीन पुनरावर्ती है।
#B: परिमित योग Σ_y<z ψ(x, y) और उत्पाद Π_y<zψ(x, y) ψ में प्राचीन पुनरावर्ती हैं।
#C: एक विधेय पी कार्यों χ प्रतिस्थापन द्वारा प्राप्त कियाχ₁,..., χ_m एक विधेय के संबंधित चर के लिए क्यू χ में प्राचीन पुनरावर्ती है χ₁,..., χ_m, Q
#D: निम्नलिखित विधेय Q और R में प्राचीन पुनरावर्ती हैं:

NOT_Q('x') .

* Q OR R: Q(x) V R(x),

* Q और R: Q(x) & R(x),

Q का तात्पर्य R: Q('x') → R('x')
Q, R के समतुल्य है: Q('x') ≡ R('x')

#E: निम्नलिखित विधेय R विधेय में प्राचीन पुनरावर्ती हैं:

(Ey)_y<z R(x, y) जहां(Ey)_y<z इंगित करता है कि कम से कम एक y उपस्थित है जो कि z से कम है
(y)_y<z R(x, y) जहां (y)_y<z सभी y के लिए z से कम दर्शाता है यह सच है कि
μy_y<z R(x, y)। ऑपरेटर μy_y<z R(x, y) तथाकथित न्यूनीकरण- या mu-ऑपरेटर का एक बाध्य रूप है: z से कम y के न्यूनतम मान के रूप में परिभाषित किया गया है जैसे कि R(x, y) सत्य है; या z यदि ऐसा कोई मान नहीं है।

#F: स्थितियों द्वारा परिभाषा: इस प्रकार परिभाषित फ़ंक्शन, जहाँ Q₁, ..., Q_m पारस्परिक रूप से अनन्य विधेय हैं (या"ψ(x) पहले खंड द्वारा दिया गया मान होगा जो लागू होता है), φ में प्राचीन पुनरावर्ती है φ₁, ..., Q₁, ... Q_m:

φ(x) =

फी₁(एक्स) यदि क्यू₁(एक्स) सच है,
. . . . . . . . . . . . . . . . . . .
φ_m(एक्स) यदि क्यू_m(एक्स) सच है
φ_m+1(एक्स) अन्यथा

#G: यदि φ समीकरण को संतुष्ट करता है:

φ(y,x) = χ(y, COURSE-φ(y; x₂, ... एक्स_n ), एक्स₂, ... एक्स_n तो φ χ में प्राचीन पुनरावर्ती है। मान पाठ्यक्रम -φ(y; x_{2 to n} ) कोर्स-ऑफ-वैल्यू फ़ंक्शन मानों के अनुक्रम को एन्कोड करता है φ(0,x_{2 to n}), ..., φ(y-1,x_{2 to n}) मूल समारोह का।

== पहले क्रम के पीनो अंकगणितीय == में प्रयोग करें

प्रथम-क्रम तर्क में | प्रथम-क्रम पीआनो अंकगणित में असीमित रूप से कई चर (0-एरी प्रतीक) हैं, लेकिन कोई k-ary गैर-तार्किक प्रतीक नहीं है जिसमें k>0 S, +, *, और ≤ के अतिरिक्त है। इस प्रकार प्राचीन पुनरावर्ती कार्यों को परिभाषित करने के लिए गोडेल द्वारा निम्नलिखित चाल का उपयोग करना होगा।

अनुक्रमों के लिए गोडेल नंबरिंग का उपयोग करके, उदाहरण के लिए गोडेल के β फ़ंक्शन, संख्याओं के किसी भी परिमित अनुक्रम को एक संख्या द्वारा एन्कोड किया जा सकता है। इस तरह की संख्या किसी दिए गए एन तक प्राचीन पुनरावर्ती फ़ंक्शन का प्रतिनिधित्व कर सकती है।

चलो एच एक 1-ary प्राचीन पुनरावर्तन समारोह द्वारा परिभाषित किया गया है:

h(0)=C

h(n+1)=g(n,h(n))

जहाँ C एक नियतांक है और g पहले से परिभाषित फलन है।

प्राकृतिक संख्याओं के किसी भी क्रम के लिए गोडेल के β फ़ंक्शन का उपयोग करना (k₀, k₁, ..., k_n), प्राकृतिक संख्याएँ b और c ऐसी हैं कि, प्रत्येक i ≤ n के लिए, β(b, c, i) = k_i. इस प्रकार हम h को परिभाषित करने के लिए निम्नलिखित सूत्र का उपयोग कर सकते हैं; अधिक त्रुटिहीन रूप से, m=h(n) निम्नलिखित के लिए एक आशुलिपि है:

\exists b:\exists c:\beta (b,c,0)=C\land \forall i:(i<n)\rightarrow (\beta (b,c,i+1)=g(i,\beta (b,c,i)))\land (m=\beta (b,c,n))

और जी के बराबर, पहले से ही परिभाषित किया जा रहा है, वास्तव में कुछ अन्य पहले से परिभाषित सूत्र के लिए आशुलिपि है (जैसा कि β है, जिसका सूत्र गोडेल का β फ़ंक्शन दिया गया है)।

किसी भी k-ary प्राचीन पुनरावर्तन समारोह का सामान्यीकरण तुच्छ है।

पुनरावर्ती कार्यों से संबंध

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

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

प्रत्येक प्राचीन पुनरावर्ती क्रिया g के लिए, एक m ऐसा है कि g(n) = f(m,n) सभी n के लिए, और
प्रत्येक एम के लिए, फ़ंक्शन एच (एन) = एफ (एम, एन) प्राचीन पुनरावर्ती है।

च को प्राचीन पुनरावर्ती कार्यों को बनाने के सभी संभावित तरीकों को दोहराकर स्पष्ट रूप से बनाया जा सकता है। इस प्रकार, यह कुल प्रमाण होता है। एक विकर्ण लेम्मा तर्क का उपयोग यह दिखाने के लिए कर सकता है कि f अपने आप में पुनरावर्ती प्राचीन नहीं है: यदि ऐसा होता, तो h(n) = f(n,n)+1 होता। लेकिन यदि यह कुछ प्राचीन पुनरावर्ती फ़ंक्शन के बराबर है, तो एक एम ऐसा है कि एच (एन) = एफ (एम, एन) सभी एन के लिए, और फिर एच (एम) = एफ (एम, एम), विरोधाभास के लिए अग्रणी।

चूँकि, प्राचीन पुनरावर्ती कार्यों का सेट सभी कुल पुनरावर्ती कार्यों के सेट का सबसे बड़ा पुनरावर्ती गणनीय उपसमुच्चय नहीं है। उदाहरण के लिए, प्रमाण कुल कार्यों का सेट (पीनो अंकगणित में) भी पुनरावर्ती गणना योग्य है, क्योंकि सिद्धांत के सभी सबूतों की गणना कर सकते हैं। जबकि सभी प्राचीन पुनरावर्ती कार्य सिद्ध रूप से कुल हैं, इसका विलोम सत्य नहीं है।

सीमाएं

प्राचीन पुनरावर्ती कार्य हमारे अंतर्ज्ञान के साथ बहुत निकटता से मेल खाते हैं कि एक संगणनीय कार्य क्या होना चाहिए। निश्चित रूप से प्रारंभिक कार्य सहज रूप से संगणनीय हैं (उनकी बहुत सरलता में), और दो ऑपरेशन जिनके द्वारा कोई नया प्राचीन पुनरावर्ती कार्य बना सकता है, वे भी बहुत सीधे हैं। चूँकि, प्राचीन पुनरावर्ती कार्यों के सेट में हर संभव कुल गणना योग्य कार्य सम्मलित नहीं है - इसे कैंटर के विकर्ण तर्क के एक संस्करण के साथ देखा जा सकता है। यह तर्क कुल संगणनीय कार्य प्रदान करता है जो प्राचीन पुनरावर्ती नहीं है। सबूत का एक स्केच इस प्रकार है:

एक तर्क के आदिम पुनरावर्ती कार्य (अर्थात, एकात्मक कार्य) संगणनीय रूप से गणना हो सकते हैं। यह गणन आदिम पुनरावर्ती कार्यों की परिभाषाओं का उपयोग करता है (जो अनिवार्य रूप से रचना और आदिम पुनरावर्ती संचालन के साथ ऑपरेटरों के रूप में और परमाणुओं के रूप में बुनियादी आदिम पुनरावर्ती कार्यों के साथ अभिव्यक्ति हैं), और यह माना जा सकता है कि हर परिभाषा एक बार, भले ही एक ही हो। 'फ़ंक्शन सूची में कई बार होगा (चूंकि कई परिभाषाएं एक ही फ़ंक्शन को परिभाषित करती हैं; वास्तव में केवल पहचान फ़ंक्शन द्वारा रचने से किसी एक आदिम पुनरावर्ती फ़ंक्शन की असीम रूप से कई परिभाषाएँ उत्पन्न होती हैं)। इसका अर्थ है किn-thइस गणना में आदिम पुनरावर्ती फलन की परिभाषा प्रभावी रूप से n. से निर्धारित की जा सकती है। वास्तव में यदि कोई गोडेल नंबरिंग का उपयोग संख्याओं के रूप में परिभाषाओं को सांकेतिक शब्दों में बदलने के लिए करता है, तो यह n-thसूची में वें परिभाषा की गणना के आदिम पुनरावर्ती कार्य द्वारा की जाती है। एन। माना n. दर्शाता है fn इस परिभाषा द्वारा दिए गए यूनरी प्रिमिटिव रिकर्सिव फंक्शन को निरूपित करें।

अब "मूल्यांकनकर्ता फ़ंक्शन" को परिभाषित करें $ev$ दो तर्कों के साथ, द्वारा $ev (i, j) = f i (j)$ .स्पष्ट रूप से $ev$ कुल और संगणनीय है, क्योंकि कोई प्रभावी रूप से इसकी परिभाषा निर्धारित कर सकता है $f i$ , और एक प्राचीन पुनरावर्ती कार्य किया जा रहा है $f i$ स्वयं कुल और गणना योग्य है, इसलिए $f i (j)$ हमेशा परिभाषित और प्रभावी ढंग से संगणनीय है। हालांकि एक विकर्ण तर्क दिखाएगा कि $ev$ दो तर्कों का आदिम पुनरावर्ती नहीं है।

कल्पना करना $ev$ आदिम पुनरावर्ती थे, फिर एकात्मक कार्य $g$ द्वारा परिभाषित $g (i) = S(ev (i, i))$ आदिम पुनरावर्ती भी होगा, क्योंकि यह उत्तराधिकारी समारोह से संरचना द्वारा परिभाषित किया गया है और $ev$ .परन्तु फिर $g$ गणना में होता है, इसलिए कुछ संख्या होती है $n$ ऐसा है कि $g = f n$ . पर अब $g (n) = S(ev (n, n)) = S(f n (n)) = S(g (n))$

विरोधाभास देता है।

यह तर्क गणना योग्य (कुल) कार्यों के किसी भी वर्ग पर लागू किया जा सकता है जिसे इस तरह से गणना की जा सकती है, जैसा लेख मशीन में समझाया गया है जो हमेशा रुकता है। चूँकि ध्यान दें कि आंशिक संगणनीय कार्य (जिन्हें सभी तर्कों के लिए परिभाषित करने की आवश्यकता नहीं है) को स्पष्ट रूप से गणना की जा सकती है, उदाहरण के लिए ट्यूरिंग मशीन एन्कोडिंग की गणना करके।

कुल पुनरावर्ती लेकिन प्राचीन पुनरावर्ती कार्यों के अन्य उदाहरण ज्ञात नहीं हैं:

फ़ंक्शन जो m को एकरमैन फ़ंक्शन(m,m) में ले जाता है वह एक एकल कुल पुनरावर्ती फ़ंक्शन है जो प्राचीन पुनरावर्ती नहीं है।
पेरिस-हैरिंगटन प्रमेय में कुल पुनरावर्ती कार्य सम्मलित है जो प्राचीन पुनरावर्ती नहीं है।
सूडान समारोह
गुडस्टीन समारोह

वेरिएंट

लगातार कार्य

के बजाय $C_{n}^{k}$ , वैकल्पिक परिभाषाएँ केवल एक 0-एरी शून्य फ़ंक्शन का उपयोग करती हैं $C_{0}^{0}$ एक प्राचीन कार्य के रूप में जो हमेशा शून्य लौटाता है, और शून्य कार्य, उत्तराधिकारी कार्य और संरचना ऑपरेटर से निरंतर कार्यों का निर्माण करता है।

कमजोर प्राचीन पुनरावर्तन

1-स्थान का पूर्ववर्ती कार्य प्राचीन पुनरावर्ती है, अनुभाग #Predecessor देखें। फिशर, फिशर और बेगेल ^[4] प्रत्यावर्तन नियम से अंतर्निहित पूर्ववर्ती को हटा दिया, इसे कमजोर नियम से बदल दिया

{\begin{array}{lcl}f(0,x_{1},\ldots ,x_{k})&=&g(x_{1},\ldots ,x_{k})&{\text{and}}\\f(S(y),x_{1},\ldots ,x_{k})&=&h(S(y),f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\end{array}}

उन्होंने प्रमाण किया कि पूर्ववर्ती कार्य अभी भी परिभाषित किया जा सकता है, और इसलिए कमजोर प्राचीन पुनरावर्तन प्राचीन पुनरावर्ती कार्यों को भी परिभाषित करता है।

पुनरावृत्ति कार्य

कार्यों का उपयोग करके इसे और भी कमजोर कर रहा है $h$ arity k+1 का, हटाना $y$ और $S(y)$ के तर्कों से $h$ पूरी तरह से, हमें पुनरावृति नियम मिलता है:

${\begin{array}{lcll}f(0,x_{1},\ldots ,x_{k})&=&g(x_{1},\ldots ,x_{k})&{\textrm {and}}\\f(S(y),x_{1},\ldots ,x_{k})&=&h(f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\end{array}}$

पुनरावृत्त कार्यों के वर्ग को उसी तरह परिभाषित किया जाता है जैसे इस कमजोर नियम को छोड़कर प्राचीन पुनरावर्ती कार्यों के वर्ग को। इन्हें प्राचीन पुनरावर्ती कार्यों का उचित उपसमुच्चय माना जाता है।^[5]

अतिरिक्त प्राचीन पुनरावर्ती रूप

पुनरावर्तन के कुछ अतिरिक्त रूप भी उन कार्यों को परिभाषित करते हैं जो वास्तव में हैं

प्राचीन पुनरावर्ती इन रूपों में परिभाषाएँ खोजना आसान हो सकता है या पढ़ने या लिखने के लिए अधिक स्वाभाविक। कोर्स-ऑफ़-वैल्यू रिकर्सन प्राचीन पुनरावर्ती कार्यों को परिभाषित करता है। आपसी पुनरावर्तन के कुछ रूप प्राचीन पुनरावर्ती कार्यों को भी परिभाषित करते हैं।

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

कंप्यूटर भाषा परिभाषा

प्राचीन पुनरावर्ती प्रोग्रामिंग भाषा का एक उदाहरण वह है जिसमें बुनियादी अंकगणितीय ऑपरेटर (जैसे + और -, या ADD और SUBTRACT), सशर्त और तुलना (IF-THEN, EQUALS, LESS-THAN), और परिबद्ध लूप, जैसे बुनियादी सम्मलित हैं लूप के लिए, जहां सभी लूपों के लिए ज्ञात या गणना योग्य ऊपरी सीमा होती है (FOR i FROM 1 TO n, लूप बॉडी द्वारा न तो i और न ही संशोधित किया जा सकता है)। अधिक सामान्यता की कोई नियंत्रण संरचना, जैसे कि लूप या IF-THEN प्लस GOTO, प्राचीन पुनरावर्ती भाषा में स्वीकार नहीं की जाती है।

लूप (प्रोग्रामिंग लैंग्वेज), 1967 में अल्बर्ट आर. मेयर और डेनिस एम. रिची द्वारा प्रस्तुत किया गया,^[6] एक ऐसी भाषा है। इसकी कंप्यूटिंग शक्ति प्राचीन पुनरावर्ती कार्यों के साथ मेल खाती है। लूप भाषा का एक प्रकार है डगलस हॉफस्टाटर का ब्लूपी और गोडेल, एस्चेर, बाख में फ़्लूपी। अनबाउंड लूप्स (WHILE, GOTO) को जोड़ने से भाषा सामान्य पुनरावर्ती कार्य करती है और ट्यूरिंग पूर्णता | ट्यूरिंग-पूर्ण, जैसा कि सभी वास्तविक दुनिया की कंप्यूटर प्रोग्रामिंग भाषाएं हैं।

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

फिनिटिज्म और संगति परिणाम

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

पीआरए पीआनो अंकगणित की तुलना में बहुत कमजोर है, जो कि परिमित प्रणाली नहीं है। फिर भी, पीआरए में संख्या सिद्धांत और प्रूफ सिद्धांत में कई परिणाम सिद्ध किए जा सकते हैं। उदाहरण के लिए, गोडेल की अपूर्णता प्रमेय को निम्नलिखित प्रमेय देते हुए पीआरए में औपचारिक रूप दिया जा सकता है:

यदि T गोडेल वाक्य G_T, के साथ कुछ परिकल्पनाओं को संतुष्ट करने वाला अंकगणित का सिद्धांत है, तो पीआरए निहितार्थ Con(T)→G_T. को सिद्ध करता है।

इसी तरह, प्रूफ थ्योरी में कई सिंटैक्टिक परिणाम PRA में सिद्ध किए जा सकते हैं, जिसका अर्थ है कि आदिम पुनरावर्ती कार्य हैं जो प्रूफ के संबंधित सिंटैक्टिक ट्रांसफॉर्मेशन को अंजाम देते हैं।

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

इतिहास

पहले पुनरावर्ती परिभाषाओं का गणित में अधिक या कम औपचारिक रूप से उपयोग किया गया था, लेकिन प्राचीन पुनरावर्तन के निर्माण का पता रिचर्ड डेडेकिंड के प्रमेय 126 में लगाया गया था, जो कि सिंड अंड सोलेन डाई ज़ाहलेन था? (1888)। यह पहला काम था जिसने एक प्रमाण दिया कि एक निश्चित पुनरावर्ती निर्माण एक अद्वितीय कार्य को परिभाषित करता है।^[7]^[8]^[9]

प्राचीन पुनरावर्ती अंकगणित पहली बार 1923 में थोराल्फ़ स्कोलेम ^[10] द्वारा प्रस्तावित किया गया था।।

एकरमैन द्वारा 1928 में यह प्रमाण करने के बाद कि वर्तमान शब्दावली को रोज़ा पेटर (1934) द्वारा गढ़ा गया था कि आज जिस फ़ंक्शन का नाम उनके नाम पर रखा गया है, वह आदिम पुनरावर्ती नहीं था, एक ऐसी घटना जिसने उस समय तक नाम बदलने की आवश्यकता को प्रेरित किया जिसे केवल पुनरावर्ती कार्य कहा जाता था।^[8]^[9]

यह भी देखें

↑ Brainerd and Landweber, 1974
↑ Kleene [1952 pp. 226–227]
↑ This follows from the facts that the functions of this form are the most quickly growing primitive recursive functions, and that a function is primitive recursive if and only if its time complexity is bounded by a primitive recursive function. For the former, see Linz, Peter (2011), An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers, p. 332, ISBN 9781449615529. For the latter, see Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, p. 287, ISBN 9780191620805
↑ Fischer, Fischer & Beigel 1989.
↑ M. Fischer, R. Fischer, R. Beigel. "Primitive Recursion without Implicit Predecessor". {{cite journal}}: Cite journal requires |journal= (help)CS1 maint: multiple names: authors list (link)
↑ Meyer, Albert R.; Ritchie, Dennis M. (1967). The complexity of loop programs. ACM '67: Proceedings of the 1967 22nd national conference. doi:10.1145/800196.806014.
↑ Peter Smith (2013). An Introduction to Gödel's Theorems (2nd ed.). Cambridge University Press. pp. 98–99. ISBN 978-1-107-02284-3.
↑ ^8.0 ^8.1 George Tourlakis (2003). Lectures in Logic and Set Theory: Volume 1, Mathematical Logic. Cambridge University Press. p. 129. ISBN 978-1-139-43942-8.
↑ ^9.0 ^9.1 Rod Downey, ed. (2014). Turing's Legacy: Developments from Turing's Ideas in Logic. Cambridge University Press. p. 474. ISBN 978-1-107-04348-0.
↑ Thoralf Skolem (1923) "The foundations of elementary arithmetic" in Jean van Heijenoort, translator and ed. (1967) From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press: 302-33.

संदर्भ

Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0
Fischer, Michael J.; Fischer, Robert P.; Beigel, Richard (November 1989). "Primitive Recursion without Implicit Predecessor". ACM SIGACT News. 20 (4): 87–91. doi:10.1145/74074.74089. S2CID 33850327.
Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987. ISBN 0-387-15299-7
Stephen Kleene (1952) Introduction to Metamathematics, North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint). In Chapter XI. General Recursive Functions §57
George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70–71.
Robert I. Soare 1995 Computability and Recursion http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
Daniel Severin 2008, Unary primitive recursive functions, J. Symbolic Logic Volume 73, Issue 4, pp. 1122–1138 arXiv projecteuclid doi:10.2178/jsl/1230396909 JSTOR 275903221

[1] Brainerd and Landweber, 1974

[2] Kleene [1952 pp. 226–227]

[3] This follows from the facts that the functions of this form are the most quickly growing primitive recursive functions, and that a function is primitive recursive if and only if its time complexity is bounded by a primitive recursive function. For the former, see Linz, Peter (2011), An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers, p. 332, ISBN 9781449615529. For the latter, see Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, Oxford University Press, p. 287, ISBN 9780191620805

[FOOTNOTEFischerFischerBeigel1989-4] Fischer, Fischer & Beigel 1989.

[5] M. Fischer, R. Fischer, R. Beigel. "Primitive Recursion without Implicit Predecessor". {{cite journal}}: Cite journal requires |journal= (help)CS1 maint: multiple names: authors list (link)

[6] Meyer, Albert R.; Ritchie, Dennis M. (1967). The complexity of loop programs. ACM '67: Proceedings of the 1967 22nd national conference. doi:10.1145/800196.806014.

[Smith2013-7] Peter Smith (2013). An Introduction to Gödel's Theorems (2nd ed.). Cambridge University Press. pp. 98–99. ISBN 978-1-107-02284-3.

[Tourlakis2003-8] 8.0 ^8.1 George Tourlakis (2003). Lectures in Logic and Set Theory: Volume 1, Mathematical Logic. Cambridge University Press. p. 129. ISBN 978-1-139-43942-8.

[Downey2014-9] 9.0 ^9.1 Rod Downey, ed. (2014). Turing's Legacy: Developments from Turing's Ideas in Logic. Cambridge University Press. p. 474. ISBN 978-1-107-04348-0.

[10] Thoralf Skolem (1923) "The foundations of elementary arithmetic" in Jean van Heijenoort, translator and ed. (1967) From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press: 302-33.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 226: / Line 226: @@
 : निम्नलिखित में संक्षिप्त रूप 'x' =<sub>def</sub> एक्स<sub>1</sub>, ... एक्स<sub>n</sub>; अर्थ की आवश्यकता होने पर सबस्क्रिप्ट लागू किया जा सकता है।
-* #A: एक फ़ंक्शन φ स्पष्ट रूप से फ़ंक्शन Ψ और स्थिरांक q से निश्चित है<sub>1</sub>, ... क्यू<sub>n</sub> Ψ में प्राचीन पुनरावर्ती है।
+* #A: एक फ़ंक्शन φ स्पष्ट रूप से फ़ंक्शन Ψ और स्थिरांक q से निश्चित है q<sub>1</sub>, ... q<sub>n</sub> Ψ में प्राचीन पुनरावर्ती है।
 * #B: परिमित योग Σ<sub>y<z</sub> ψ(x, y) और उत्पाद Π<sub>y<z</sub>ψ(x, y) ψ में प्राचीन पुनरावर्ती हैं।
-* #सी: एक ''विधेय'' पी कार्यों χ प्रतिस्थापन द्वारा प्राप्त किया<sub>1</sub>,..., एच<sub>m</sub> एक विधेय के संबंधित चर के लिए क्यू χ में प्राचीन पुनरावर्ती है<sub>1</sub>,..., एच<sub>m</sub>, क्यू।
+* #C: एक ''विधेय'' पी कार्यों χ प्रतिस्थापन द्वारा प्राप्त कियाχ<sub>1</sub>,..., χ<sub>m</sub>  एक विधेय के संबंधित चर के लिए क्यू χ में प्राचीन पुनरावर्ती है χ<sub>1</sub>,..., χ<sub>m</sub>, Q
 * #D: निम्नलिखित विधेय Q और R में प्राचीन पुनरावर्ती हैं:
 ::* NOT_Q('x') .
-:: * क्यू या आर: क्यू ('एक्स') वी आर ('एक्स'),
+:: *    Q OR R: Q('''x''') V R('''x'''),
-:: * क्यू और आर: क्यू ('एक्स') और आर ('एक्स'),
+:: *   Q और R:  Q('''x''') & R('''x'''),
 ::* Q का तात्पर्य R: Q('x') → R('x')
 ::* Q, R के समतुल्य है: Q('x') ≡ R('x')
 * #E: निम्नलिखित विधेय R विधेय में प्राचीन पुनरावर्ती हैं:
-::* (अय)<sub>y<z</sub> आर (एक्स, वाई) जहां (ई)<sub>y<z</sub> इंगित करता है कि कम से कम एक y उपस्थित है जो कि z से कम है
+::* (Ey)<sub>y<z</sub> R('''x''', y) जहां(Ey)<sub>y<z</sub> इंगित करता है कि कम से कम एक y उपस्थित है जो कि z से कम है
-::* (य)<sub>y<z</sub> आर (एक्स, वाई) जहां (वाई)<sub>y<z</sub> सभी y के लिए z से कम दर्शाता है यह सच है कि
+::* (y)<sub>y<z</sub> R('''x''', y) जहां  (y)<sub>y<z</sub> सभी y के लिए z से कम दर्शाता है यह सच है कि
-::*<sub>y<z</sub> आर (एक्स, वाई)। ऑपरेटर μy<sub>y<z</sub> R(x, y) तथाकथित न्यूनीकरण- या mu-ऑपरेटर का एक ''बाध्य'' रूप है: z से कम y के न्यूनतम मान के रूप में परिभाषित किया गया है जैसे कि R(x, y) सत्य है; या z यदि ऐसा कोई मान नहीं है।
+::*μy<sub>y<z</sub> R('''x''', y)। ऑपरेटर μy<sub>y<z</sub> R('''x''', y) तथाकथित न्यूनीकरण- या mu-ऑपरेटर का एक ''बाध्य'' रूप है: z से कम y के न्यूनतम मान के रूप में परिभाषित किया गया है जैसे कि R('''x''', y) सत्य है; या z यदि ऐसा कोई मान नहीं है।
-* #F: स्थितियों द्वारा परिभाषा: इस प्रकार परिभाषित फ़ंक्शन, जहाँ Q<sub>1</sub>, ..., क्यू<sub>m</sub> पारस्परिक रूप से अनन्य विधेय हैं (या ψ('x') पहले खंड द्वारा दिया गया मान होगा जो लागू होता है), φ में प्राचीन पुनरावर्ती है<sub>1</sub>, ..., क्यू<sub>1</sub>, ... क्यू<sub>m</sub>:
+* #F: स्थितियों द्वारा परिभाषा: इस प्रकार परिभाषित फ़ंक्शन, जहाँ Q<sub>1</sub>, ..., Q<sub>m</sub> पारस्परिक रूप से अनन्य विधेय हैं (या"ψ('''x''') पहले खंड द्वारा दिया गया मान होगा जो लागू होता है), φ में प्राचीन पुनरावर्ती है φ<sub>1</sub>, ..., Q<sub>1</sub>, ... Q<sub>m</sub>:
 :: φ(x) =
 ::* फी<sub>1</sub>(एक्स) यदि क्यू<sub>1</sub>(एक्स) सच है,
@@ Line 246: / Line 246: @@
 ::* φ<sub>m+1</sub>(एक्स) अन्यथा
 * #G: यदि φ समीकरण को संतुष्ट करता है:
-:: φ(y,x) = χ(y, COURSE-φ(y; x<sub>2</sub>, ... एक्स<sub>n</sub> ), एक्स<sub>2</sub>, ... एक्स<sub>n</sub> तो φ χ में प्राचीन पुनरावर्ती है। मान पाठ्यक्रम-φ(y; x<sub>2 to n</sub> ) कोर्स-ऑफ-वैल्यू फ़ंक्शन मानों के अनुक्रम को एन्कोड करता है φ(0,x<sub>2 to n</sub>), ..., φ(y-1,x<sub>2 to n</sub>) मूल समारोह का।
+:: φ(y,x) = χ(y, COURSE-φ(y; x<sub>2</sub>, ... एक्स<sub>n</sub> ), एक्स<sub>2</sub>, ... एक्स<sub>n</sub> तो φ χ में प्राचीन पुनरावर्ती है। मान पाठ्यक्रम -φ(y; x<sub>2 to n</sub> ) कोर्स-ऑफ-वैल्यू फ़ंक्शन मानों के अनुक्रम को एन्कोड करता है φ(0,'''x'''<sub>2 to n</sub>), ..., φ(y-1,'''x'''<sub>2 to n</sub>) मूल समारोह का।
 == पहले क्रम के पीनो अंकगणितीय == में प्रयोग करें
-{{expert needed|computer science|section|reason=properly explain the purpose of using the β function (the text only explains *how* it is used, not *what for* - I guess in some Gödelian (un)computability proof)|date=November 2021}} प्रथम-क्रम तर्क में | प्रथम-क्रम पीआनो अंकगणित में असीमित रूप से कई चर (0-एरी प्रतीक) हैं, लेकिन कोई arity|k-ary गैर-तार्किक प्रतीक नहीं है जिसमें k>0 S, +, *, और ≤ के अतिरिक्त है। इस प्रकार प्राचीन पुनरावर्ती कार्यों को परिभाषित करने के लिए गोडेल द्वारा निम्नलिखित चाल का उपयोग करना होगा।
+{{expert needed|computer science|section|reason=properly explain the purpose of using the β function (the text only explains *how* it is used, not *what for* - I guess in some Gödelian (un)computability proof)|date=November 2021}} प्रथम-क्रम तर्क में | प्रथम-क्रम पीआनो अंकगणित में असीमित रूप से कई चर (0-एरी प्रतीक) हैं, लेकिन कोई  k-ary गैर-तार्किक प्रतीक नहीं है जिसमें k>0 S, +, *, और ≤ के अतिरिक्त है। इस प्रकार प्राचीन पुनरावर्ती कार्यों को परिभाषित करने के लिए गोडेल द्वारा निम्नलिखित चाल का उपयोग करना होगा।
 अनुक्रमों के लिए गोडेल नंबरिंग का उपयोग करके, उदाहरण के लिए गोडेल के β फ़ंक्शन, संख्याओं के किसी भी परिमित अनुक्रम को एक संख्या द्वारा एन्कोड किया जा सकता है। इस तरह की संख्या किसी दिए गए एन तक प्राचीन पुनरावर्ती फ़ंक्शन का प्रतिनिधित्व कर सकती है।
-चलो एच एक 1-एरी प्राचीन पुनरावर्तन समारोह द्वारा परिभाषित किया गया है:
+चलो एच एक 1-ary प्राचीन पुनरावर्तन समारोह द्वारा परिभाषित किया गया है:
 :<math> h(0) = C</math>
 :<math> h(n+1) = g(n,h(n))</math>
 जहाँ C एक नियतांक है और g पहले से परिभाषित फलन है।
-प्राकृतिक संख्याओं के किसी भी क्रम के लिए गोडेल के β फ़ंक्शन का उपयोग करना (k<sub>0</sub>, क<sub>1</sub>, ..., क<sub>n</sub>), प्राकृतिक संख्याएँ b और c ऐसी हैं कि, प्रत्येक i ≤ n के लिए, β(b, c, i) = k<sub>i</sub>. इस प्रकार हम h को परिभाषित करने के लिए निम्नलिखित सूत्र का उपयोग कर सकते हैं; अधिक त्रुटिहीन रूप से, m=h(n) निम्नलिखित के लिए एक आशुलिपि है:
+प्राकृतिक संख्याओं के किसी भी क्रम के लिए गोडेल के β फ़ंक्शन का उपयोग करना (k<sub>0</sub>, k<sub>1</sub>, ..., k<sub>n</sub>), प्राकृतिक संख्याएँ b और c ऐसी हैं कि, प्रत्येक i ≤ n के लिए, β(b, c, i) = k<sub>i</sub>. इस प्रकार हम h को परिभाषित करने के लिए निम्नलिखित सूत्र का उपयोग कर सकते हैं; अधिक त्रुटिहीन रूप से, m=h(n) निम्नलिखित के लिए एक आशुलिपि है:
 :<math>\exists b: \exists c: \beta(b, c, 0) = C \land \forall i: (i<n) \rightarrow (\beta(b, c, i+1) = g(i,\beta(b, c, i))) \land (m = \beta(b, c, n))</math>
@@ Line 267: / Line 267: @@
 == पुनरावर्ती कार्यों से संबंध ==
-[[आंशिक पुनरावर्ती कार्य]]ों के व्यापक वर्ग को [[ऑपरेटर में]] की शुरुआत करके परिभाषित किया गया है। इस ऑपरेटर के उपयोग के परिणामस्वरूप आंशिक फ़ंक्शन हो सकता है, अर्थात, प्रत्येक तर्क के लिए अधिकतम एक मान के साथ संबंध, लेकिन किसी भी तर्क के लिए कोई मान आवश्यक नहीं है (फ़ंक्शन का डोमेन देखें)। एक समतुल्य परिभाषा बताती है कि एक आंशिक पुनरावर्ती कार्य वह है जिसे [[ट्यूरिंग मशीन]] द्वारा गणना की जा सकती है। टोटल रिकर्सिव फंक्शन एक आंशिक रिकर्सिव फंक्शन है जिसे हर इनपुट के लिए परिभाषित किया गया है।
+[[आंशिक पुनरावर्ती कार्य|आंशिक पुनरावर्ती]] कार्यो के व्यापक वर्ग को [[ऑपरेटर में]] की शुरुआत करके परिभाषित किया गया है। इस ऑपरेटर के उपयोग के परिणामस्वरूप आंशिक फ़ंक्शन हो सकता है, अर्थात, प्रत्येक तर्क के लिए अधिकतम एक मान के साथ संबंध, लेकिन किसी भी तर्क के लिए कोई मान आवश्यक नहीं है (फ़ंक्शन का डोमेन देखें)। एक समतुल्य परिभाषा बताती है कि एक आंशिक पुनरावर्ती कार्य वह है जिसे [[ट्यूरिंग मशीन]] द्वारा गणना की जा सकती है। टोटल रिकर्सिव फंक्शन एक आंशिक रिकर्सिव फंक्शन है जिसे हर इनपुट के लिए परिभाषित किया गया है।
 प्रत्येक प्राचीन पुनरावर्ती कार्य कुल पुनरावर्ती है, लेकिन सभी कुल पुनरावर्ती कार्य प्राचीन पुनरावर्ती नहीं हैं। [[एकरमैन समारोह]] ए (एम, एन) कुल पुनरावर्ती फ़ंक्शन (वास्तव में, सिद्ध करने योग्य कुल) का एक प्रसिद्ध उदाहरण है, जो प्राचीन पुनरावर्ती नहीं है। एकरमैन फ़ंक्शन का उपयोग करके कुल पुनरावर्ती कार्यों के सबसेट के रूप में प्राचीन पुनरावर्ती कार्यों का एक लक्षण वर्णन है। यह लक्षण वर्णन बताता है कि एक फ़ंक्शन प्राचीन पुनरावर्ती है यदि और केवल यदि कोई प्राकृतिक संख्या m है जैसे कि फ़ंक्शन की गणना ट्यूरिंग मशीन द्वारा की जा सकती है जो हमेशा A(m,n) या उससे कम चरणों में रुकती है, जहां n का योग है प्राचीन पुनरावर्ती क्रिया के तर्क।<ref>This follows from the facts that the functions of this form are the most quickly growing primitive recursive functions, and that a function is primitive recursive if and only if its time complexity is bounded by a primitive recursive function. For the former, see {{citation|title=An Introduction to Formal Languages and Automata|first=Peter|last=Linz|publisher=Jones & Bartlett Publishers|year=2011|isbn=9781449615529|page=332|url=https://books.google.com/books?id=hsxDiWvVdBcC&pg=PA332}}. For the latter, see {{citation|title=The Nature of Computation|first1=Cristopher|last1=Moore|author1-link=Cristopher Moore|first2=Stephan|last2=Mertens|publisher=Oxford University Press|year=2011|isbn=9780191620805|page=287|url=https://books.google.com/books?id=jnGKbpMV8xoC&pg=PA287}}</ref>
@@ Line 313: / Line 313: @@
 <math>\begin{array}{lcll} f(0,x_1,\ldots,x_k) & = & g(x_1,\ldots,x_k) &\textrm{and} \\ f(S(y),x_1,\ldots,x_k) & = & h(f(y,x_1,\ldots,x_k),x_1,\ldots,x_k) \end{array}</math>
 पुनरावृत्त कार्यों के वर्ग को उसी तरह परिभाषित किया जाता है जैसे इस कमजोर नियम को छोड़कर प्राचीन पुनरावर्ती कार्यों के वर्ग को। इन्हें प्राचीन पुनरावर्ती कार्यों का उचित उपसमुच्चय माना जाता है।<ref>{{Cite document|last=M. Fischer, R. Fischer, R. Beigel|title=Primitive Recursion without Implicit Predecessor}}</ref>
@@ Line 319: / Line 321: @@
 पुनरावर्तन के कुछ अतिरिक्त रूप भी उन कार्यों को परिभाषित करते हैं जो वास्तव में हैं
-प्राचीन पुनरावर्ती। इन रूपों में परिभाषाएँ खोजना आसान हो सकता है या
+प्राचीन पुनरावर्ती इन रूपों में परिभाषाएँ खोजना आसान हो सकता है या
 पढ़ने या लिखने के लिए अधिक स्वाभाविक। [[कोर्स-ऑफ़-वैल्यू रिकर्सन]] प्राचीन पुनरावर्ती कार्यों को परिभाषित करता है। [[आपसी पुनरावर्तन]] के कुछ रूप प्राचीन पुनरावर्ती कार्यों को भी परिभाषित करते हैं।

Anonymous

Search