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

Latest revision as of 16:55, 24 February 2023

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

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

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

परिभाषा

प्राचीन पुनरावर्ती फलन तर्कों की एक निश्चित संख्या लेता है, प्रत्येक प्राकृतिक संख्या (गैर-नकारात्मक पूर्णांक: {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 से दर्शाए गए हैं₁, ...,x_k, फॉर-लूप के साथ निरूपित, फॉर-लूप के लिए प्रारंभिक शर्तों का एक सेट है, जिसका उपयोग इसके द्वारा गणना के दौरान किया जा सकता है, लेकिन जो इसके द्वारा अपरिवर्तनीय हैं। फलन g और h समीकरणों के दाईं ओर जो f को परिभाषित करते हैं, लूप के शरीर का प्रतिनिधित्व करते हैं, जो गणना करता है। प्रारंभिक गणना करने के लिए फलन g का उपयोग केवल एक बार किया जाता है। लूप के बाद के चरणों की गणना एच द्वारा की जाती है। एच के पहले पैरामीटर को फॉर-लूप के इंडेक्स का "वर्तमान" मान खिलाया जाता है। h का दूसरा पैरामीटर पिछले चरणों से फॉर-लूप की पिछली गणनाओं का परिणाम है। एच के लिए बाकी पैरामीटर पहले बताए गए फॉर-लूप के लिए अपरिवर्तनीय प्रारंभिक शर्तें हैं। उनका उपयोग 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}}

कटा हुआ घटाव

सीमित घटाव फलन (जिसे मोनस भी कहा जाता है, और निरूपित किया जाता है ${\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): (पूर्ववर्ती या कमी): यदि 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): "लंबाई" या गैर-लुप्त होने वाले xपोनेंट्स की संख्या
lo(a, b): (आधार b का लघुगणक): यदि a, b > 1 तो सबसे बड़ा x ऐसा है कि b^x | a अन्य 0

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

#A: एक फलन φ स्पष्ट रूप से फलन Ψ और स्थिरांक q से निश्चित है q₁, ... q_n Ψ में प्राचीन पुनरावर्ती है।
#B: परिमित योग Σ_y<z ψ(x, y) और उत्पाद Π_y<zψ(x, y) ψ में प्राचीन पुनरावर्ती हैं।
#C: एक विधेय पी कार्यों χ प्रतिस्थापन द्वारा प्राप्त कियाχ₁,..., χ_m एक विधेय के संबंधित चर के लिए Q χ में प्राचीन पुनरावर्ती है χ₁,..., χ_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: स्थितियों द्वारा परिभाषा: इस प्रकार परिभाषित फ़ंक्शन, जहां Q1, ..., Q₁, ..., Q_m पारस्परिक रूप से अनन्य विधेय हैं पारस्परिक रूप से अनन्य विधेय हैं (या "ψ(x) में पहले खंड द्वारा दिया गया मान होगा जो लागू होता है), φ₁, ..., Q₁, ... Q_mमें प्राचीन पुनरावर्ती है:

φ(x) =

φ₁(x) यदि Q₁ (x) सच है,
. . . . . . . . . . . . . . . . . . .
φ_m(x) यदि Q_m(x) सच है
φ_m+1(x) अन्यथा

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

φ(y,x) = χ(y, COURSE-φ(y; x₂, ... x_n ), x₂, ... x_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 प्रारंभिक पुनरावर्तन फलन का सामान्यीकरण तुच्छ है।

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

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

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

मौलिक पुनरावर्ती फलनों की महत्वपूर्ण संपत्ति यह है कि वे सभी कुल पुनरावर्ती कार्यों के सेट का पुनरावर्ती रूप से गणना करने योग्य उपसमुच्चय हैं (जो स्वयं पुनरावर्ती गणना योग्य नहीं है)। इसका मतलब यह है कि एक एकल संगणनीय कार्य f(m,n) है जो मौलिक पुनरावर्ती फलनों की गणना करता है, अर्थात्:

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

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

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

सीमाएं

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

तर्क के आदिम पुनरावर्ती कार्य (अर्थात, एकात्मक कार्य) संगणनीय रूप से गणना हो सकते हैं। यह गणन आदिम पुनरावर्ती कार्यों की परिभाषाओं का उपयोग करता है (जो अनिवार्य रूप से रचना और आदिम पुनरावर्ती संचालन के साथ ऑपरेटरों के रूप में और परमाणुओं के रूप में बुनियादी आदिम पुनरावर्ती कार्यों के साथ अभिव्यक्ति हैं), और यह माना जा सकता है कि हर परिभाषा एक बार, भले ही एक ही हो। 'फ़ंक्शन सूची में कई बार होगा (चूंकि कई परिभाषाएं एक ही फ़ंक्शन को परिभाषित करती हैं; वास्तव में केवल पहचान फ़ंक्शन द्वारा रचने से किसी एक आदिम पुनरावर्ती फ़ंक्शन की असीम रूप से कई परिभाषाएँ उत्पन्न होती हैं)। इसका अर्थ है कि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 1: / Line 1: @@
 {{Short description|Function computable with bounded loops}}
-कम्प्यूटेबिलिटी सिद्धांत में, एक आदिम पुनरावर्ती कार्य, मोटे तौर पर बोलना, एक ऐसा कार्य है जिसकी गणना एक [[कंप्यूटर प्रोग्राम]] द्वारा की जा सकती है जिसका [[पाश (प्रोग्रामिंग)]] सभी फॉर लूप हैं | लूप के लिए (यानी, लूप में प्रवेश करने से पहले प्रत्येक लूप के पुनरावृत्तियों की संख्या की ऊपरी सीमा निर्धारित की जा सकती है)। आदिम पुनरावर्ती कार्य उन [[सामान्य पुनरावर्ती कार्य]]ों का एक सख्त उपसमुच्चय बनाते हैं जो कुल कार्य भी हैं।
+कम्प्यूटेबिलिटी सिद्धांत में, '''मौलिक पुनरावर्ती फलन''', एक ऐसा कार्य है जिसकी गणना [[कंप्यूटर प्रोग्राम]] द्वारा की जा सकती है, जिसके लूप सभी "फॉर" लूप हैं लूप के लिए (अर्थात, प्रत्येक लूप के पुनरावृत्तियों की संख्या की ऊपरी सीमा पहले निर्धारित की जा सकती है) मौलिक पुनरावर्ती फलन उन [[सामान्य पुनरावर्ती कार्य|सामान्य पुनरावर्ती कार्यो]] का एक सख्त उपसमुच्चय बनाते हैं जो कुल कार्य भी हैं।
-आदिम पुनरावर्ती कार्यों का महत्व इस तथ्य में निहित है कि [[संख्या सिद्धांत]] (और आमतौर पर गणित में) में अध्ययन किए जाने वाले अधिकांश संगणनीय कार्य आदिम पुनरावर्ती हैं। उदाहरण के लिए, योग और [[विभाजन (गणित)]], क्रमगुणित और चरघातांकी फलन, और फलन जो ''n'' अभाज्य देता है, सभी आदिम पुनरावर्ती हैं।<ref>Brainerd and Landweber, 1974</ref> वास्तव में, यह दिखाने के लिए कि एक संगणनीय कार्य आदिम पुनरावर्ती है, यह दिखाने के लिए पर्याप्त है कि इसकी [[समय जटिलता]] इनपुट आकार के एक आदिम पुनरावर्ती कार्य से ऊपर है।{{cn|reason=Give a source for a proof.|date=November 2021}} इसलिए यह इतना आसान नहीं है कि एक संगणनीय कार्य तैयार किया जा सके जो आदिम पुनरावर्ती नहीं है; कुछ उदाहरण अनुभाग में दिखाए गए हैं {{slink||Limitations}} नीचे।
+मौलिक पुनरावर्ती फलनों का महत्व इस तथ्य में निहित है कि [[संख्या सिद्धांत]] (और सामान्यतः गणित में) में अध्ययन किए जाने वाले अधिकांश संगणनीय कार्य प्राचीन पुनरावर्ती हैं। उदाहरण के लिए, योग और [[विभाजन (गणित)]], क्रमगुणित और चरघातांकी फलन, और जो फलन ''n'' अभाज्य को लौटाता है, सभी प्राचीन पुनरावर्ती हैं। <ref>Brainerd and Landweber, 1974</ref> वास्तव में, यह दिखाने के लिए कि संगणनीय कार्य प्राचीन पुनरावर्ती है, यह दिखाने के लिए पर्याप्त है कि इसकी समय जटिलता इनपुट आकार के मौलिक पुनरावर्ती फलन से ऊपर है। इसलिए संगणनीय कार्य को तैयार करना इतना आसान नहीं है कि प्राचीन पुनरावर्ती नहीं है; कुछ उदाहरण नीचे अनुभाग § सीमाएँ में दिखाए गए हैं।
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में आदिम पुनरावर्ती कार्यों के सेट को [[पीआर (जटिलता)]] के रूप में जाना जाता है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में मौलिक पुनरावर्ती फलनों के सेट को [[पीआर (जटिलता)]] के रूप में जाना जाता है।
 == परिभाषा ==
-एक आदिम पुनरावर्ती फ़ंक्शन तर्कों की एक निश्चित संख्या लेता है, प्रत्येक एक [[प्राकृतिक संख्या]] (गैर-नकारात्मक पूर्णांक: {0, 1, 2, ...}), और एक प्राकृतिक संख्या देता है। यदि यह n तर्क लेता है तो इसे n-[[arity]] कहा जाता है।
+प्राचीन पुनरावर्ती फलन तर्कों की एक निश्चित संख्या लेता है, प्रत्येक [[प्राकृतिक संख्या]] (गैर-नकारात्मक पूर्णांक: {0, 1, 2, ...}), और एक प्राकृतिक संख्या देता है। यदि यह ''n'' तर्क लेता है तो इसे ''n''-ary कहा जाता है।
-बुनियादी आदिम पुनरावर्ती कार्य इन [[स्वयंसिद्ध]]ों द्वारा दिए गए हैं:
+बुनियादी मौलिक पुनरावर्ती फलन इन [[स्वयंसिद्ध|स्वयंसिद्धों]] द्वारा दिए गए हैं:
 {{ordered list|start=1
-|1=''Constant functions {{mvar|C{{su|b=n|p=k}}}}: प्रत्येक प्राकृतिक संख्या के लिए {{mvar|n}} और हर {{mvar|k}}, k-ary नियतांक फलन, द्वारा परिभाषित <math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  n</math>, आदिम पुनरावर्ती है।
+|1='लगातार कार्य Ck
+n: प्रत्येक प्राकृतिक संख्या के लिए  {{mvar|n}} और हर {{mvar|k}},के लिए k-ary नियतांक फलन, द्वारा परिभाषित <math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  n</math>, प्राचीन पुनरावर्ती है।
-| 2=उत्तराधिकारी फलन: 1-ऐरी उत्तरवर्ती फलन S, जो अपने तर्क का परवर्ती लौटाता है (पीनो अभिधारणाएं देखें), अर्थात्, <math>S(x) \ \stackrel{\mathrm{def}}{=}\  x + 1</math>, आदिम पुनरावर्ती है।
+| 2=उत्तराधिकारी फलन: 1-ऐरी उत्तरवर्ती फलन S, जो अपने तर्क का परवर्ती लौटाता है (पीनो अभिधारणाएं देखें), अर्थात्, <math>S(x) \ \stackrel{\mathrm{def}}{=}\  x + 1</math>, प्राचीन पुनरावर्ती है।
-| 3=प्रोजेक्शन फंक्शन <math>P_i^k</math>: सभी प्राकृतिक संख्याओं के लिए <math>i, k</math> ऐसा है कि <math>1\le i\le k</math>, k-ary फ़ंक्शन द्वारा परिभाषित <math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  x_i</math> आदिम पुनरावर्ती है।
+| 3=प्रोजेक्शन फंक्शन <math>P_i^k</math>: सभी प्राकृतिक संख्याओं के लिए <math>i, k</math> ऐसा है कि <math>1\le i\le k</math>, k-ary फ़ंक्शन द्वारा परिभाषित <math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  x_i</math> प्राचीन पुनरावर्ती है।
 }}
-इन स्वयंसिद्धों द्वारा दिए गए ऑपरेशन (गणित) को लागू करके अधिक जटिल आदिम पुनरावर्ती कार्य प्राप्त किए जा सकते हैं:
+इन स्वयंसिद्धों द्वारा दिए गए कार्यों को लागू करके अधिक जटिल मौलिक पुनरावर्ती फलन प्राप्त किए जा सकते हैं:
 {{ordered list|start=4
-| 4=''Composition operator'' <math>\circ\,</math> (also called the ''substitution operator''): Given an ''m''-ary function <math>h(x_1,\ldots,x_m)\,</math> and ''m'' ''k''-ary functions <math>g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k)</math>: <math display="block">h \circ (g_1, \ldots, g_m) \ \stackrel{\mathrm{def}}{=}\ f, \quad\text{जहां}\quad f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k)) ।</गणित>
+| 4=''मौलिक पुनरावर्ती फलन'' {{mvar|&rho;}}: ''K''-ary फलन दिया गया है <math>g(x_1,\ldots,x_k)\,</math> और (''k''&nbsp;+&nbsp;2)-एरी फ़ंक्शन <math>h(y,z,x_1,\ldots,x_k)\,</math>:<math display="block">\begin{align}
-| 5=आदिम रिकर्सन ऑपरेटर {{mvar|&rho;}}: के-एरी फ़ंक्शन दिया गया है <math>g(x_1,\ldots,x_k)\,</math> और (के + 2) -एरी फ़ंक्शन <math>h(y,z,x_1,\ldots,x_k)\,</math>:<math display="block">\begin{align}
               \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{align}</math>
-व्याख्या:
+''व्याख्या:''
-फ़ंक्शन f एक for लूप के रूप में कार्य करता है | for-loop 0 से इसके पहले तर्क के मान तक। F के लिए शेष तर्क, यहाँ x से दर्शाए गए हैं<sub>1</sub>, ..., एक्स<sub>''k''</sub>, फॉर-लूप के लिए प्रारंभिक शर्तों का एक सेट है जो गणना के दौरान इसके द्वारा उपयोग किया जा सकता है लेकिन जो इसके द्वारा अपरिवर्तनीय हैं। फ़ंक्शन g और h समीकरणों के दाईं ओर जो f को परिभाषित करते हैं, लूप के शरीर का प्रतिनिधित्व करते हैं, जो गणना करता है। प्रारंभिक गणना करने के लिए फ़ंक्शन g का उपयोग केवल एक बार किया जाता है। लूप के बाद के चरणों की गणना h द्वारा की जाती है। h का पहला पैरामीटर फॉर-लूप के इंडेक्स का वर्तमान मान फीड करता है। एच का दूसरा पैरामीटर पिछले चरणों से फॉर-लूप की पिछली गणनाओं का परिणाम है। एच के लिए बाकी पैरामीटर पहले बताए गए फॉर-लूप के लिए अपरिवर्तनीय प्रारंभिक शर्तें हैं। उनका उपयोग h द्वारा गणना करने के लिए किया जा सकता है लेकिन वे स्वयं h द्वारा परिवर्तित नहीं होंगे।
+फलन&nbsp;''f'' [[लूप के लिए|फॉर-लूप]] के रूप में 0 से इसके पहले तर्क के मान तक कार्य करता है। &nbsp;''f'' के लिए बाकी तर्क, यहां ''x''<sub>1</sub>,&nbsp;...,&nbsp;''x''<sub>''k' से दर्शाए गए हैं '</sub>, फॉर-लूप के लिए प्रारंभिक शर्तों का एक सेट है जो गणना के दौरान इसके द्वारा उपयोग किया जा सकता है लेकिन जो इसके द्वारा अपरिवर्तनीय हैं। फ़ंक्शन ''g'' और ''h'' समीकरणों के दाईं ओर जो ''f'' को परिभाषित करते हैं, लूप के शरीर का प्रतिनिधित्व करते हैं, जो गणना करता है। फ़ंक्शन&nbsp;''g'' का उपयोग प्रारंभिक गणना करने के लिए केवल एक बार किया जाता है। लूप के बाद के चरणों की गणना&nbsp;''h'' द्वारा की जाती है। &nbsp;''h'' का पहला पैरामीटर फॉर-लूप के इंडेक्स के "वर्तमान" मान को फीड किया जाता है। &nbsp;''h'' का दूसरा पैरामीटर पिछले चरणों से, फॉर-लूप की पिछली गणनाओं का परिणाम है। &nbsp;''h'' के लिए बाकी पैरामीटर पहले बताए गए फॉर-लूप के लिए अपरिवर्तनीय प्रारंभिक शर्तें हैं। उनका उपयोग&nbsp;''h'' द्वारा गणना करने के लिए किया जा सकता है लेकिन वे स्वयं&nbsp;''h'' द्वारा परिवर्तित नहीं होंगे। |फलन f 0 से इसके पहले तर्क के मान तक फॉर-लूप के रूप में कार्य करता है।  f के लिए बाकी तर्क, यहाँ x से दर्शाए गए हैं<sub>1</sub>, ...,x<sub>''k''</sub>, फॉर-लूप के साथ निरूपित, फॉर-लूप के लिए प्रारंभिक शर्तों का एक सेट है, जिसका उपयोग इसके द्वारा गणना के दौरान किया जा सकता है, लेकिन जो इसके द्वारा अपरिवर्तनीय हैं। फलन g और h समीकरणों के दाईं ओर जो f को परिभाषित करते हैं, लूप के शरीर का प्रतिनिधित्व करते हैं, जो गणना करता है। प्रारंभिक गणना करने के लिए फलन g का उपयोग केवल एक बार किया जाता है। लूप के बाद के चरणों की गणना एच द्वारा की जाती है। एच के पहले पैरामीटर को फॉर-लूप के इंडेक्स का "वर्तमान" मान खिलाया जाता है। h का दूसरा पैरामीटर पिछले चरणों से फॉर-लूप की पिछली गणनाओं का परिणाम है। एच के लिए बाकी पैरामीटर पहले बताए गए फॉर-लूप के लिए अपरिवर्तनीय प्रारंभिक शर्तें हैं। उनका उपयोग h द्वारा गणना करने के लिए किया जा सकता है लेकिन वे स्वयं h द्वारा परिवर्तित नहीं होंगे।
 }}
-'आदिम पुनरावर्ती कार्य' मूल कार्य हैं और इन कार्यों को सीमित संख्या में लागू करके मूल कार्यों से प्राप्त किए जाते हैं।
+'मौलिक पुनरावर्ती फलन' मूल कार्य हैं और इन कार्यों को सीमित संख्या में लागू करके मूल कार्यों से प्राप्त किए जाते हैं।
 == उदाहरण ==
@@ Line 35: / Line 35: @@
 {{unordered list
-|<math>C_0^1</math> is a 1-ary function which returns <math>0</math> for every input: <math>C_0^1(x) = 0</math>.
+|<math>C_0^1</math> एक 1-एरी फलन है जो रिटर्न देता है <math>0</math>प्रत्येक इनपुट के लिए:<math>C_ 0^1 (x) = 0</math>.
-|<math>C_1^1</math> is a 1-ary function which returns <math>1</math> for every input: <math>C_1^1(x) = 1</math>.
+|<math>C_1^1</math> एक 1-एरी फलन है जो रिटर्न देता है
-|<math>C_3^0</math> is a 0-ary function, i.e. a constant: <math>C_3^0 = 3</math>.
+प्रत्येक इनपुट के लिए :<math></math> <math>C_1^1(x) = 1</math>.
-|<math>P_1^1</math> is the identity function on the natural numbers: <math>P_1^1(x) = x</math>.
+|<math>C_3^0</math> एक 0-एरी फलन है, यानी स्थिर:<math>C_3^0 = 3</math>.
-|<math>P_1^2</math> and <math>P_2^2</math> is the left and right projection on natural number pairs, respectively: <math>P_1^2(x,y) = x</math> and <math>P_2^2(x,y) = y</math>.
+|<math>P_1^1</math> प्राकृतिक संख्याओं पर पहचान कार्य है:: <math>P_1^1(x) = x</math>.
-|<math>S \circ S</math> is a 1-ary function that adds 2 to its input, <math>(S \circ S)(x) = x+2</math>.
+|<math>P_1^2</math> and <math>P_2^2</math> प्राकृतिक संख्या युग्मों पर क्रमशः बाएँ और दाएँ प्रक्षेपण है: <math>P_1^2(x,y) = x</math> and <math>P_2^2(x,y) = y</math>.
-|<math>S \circ C_0^1</math> is a 1-ary function which returns 1 for every input: <math>(S \circ C_0^1)(x) = S(C_0^1(x)) = S(0) = 1</math>. That is, <math>S \circ C_0^1</math> and <math>C_1^1</math> are the same function: <math>S \circ C_0^1 = C_1^1</math>. In a similar way, every <math>C_n^1</math> can be expressed as a composition of appropriately many <math>S</math> and <math>C_0^1</math>.
+|<math>S \circ S</math>एक 1-एरी फलन है जो इसके इनपुट में 2 जोड़ता है,<math>(S \circ S)(x) = x+2</math>.
+|<math>S \circ C_0^1</math>
+एक 1-एरी फलन है जो प्रत्येक इनपुट के लिए 1 लौटाता है: <math>(S \circ C_0^1)(x) = S(C_0^1(x)) = S(0) = 1</math>. That is, <math>S \circ C_0^1</math>और <math>C_1^1</math> एक ही कार्य हैं: <math>S \circ C_0^1 = C_1^1</math>. इसी तरह, हर<math>C_n^1</math> उचित रूप से कई की रचना के रूप में व्यक्त किया जा सकता है <math>S</math>और <math>C_0^1</math>.
 }}
 === जोड़ ===
--एरी फ़ंक्शन की परिभाषा <math>Add</math>, इसके तर्कों के योग की गणना करने के लिए, प्रिमिटिव रिकर्सन ऑपरेटर का उपयोग करके प्राप्त किया जा सकता है <math>\rho</math>. इसके लिए, प्रसिद्ध समीकरण
+-एरी फलन की परिभाषा <math>Add</math>, इसके तर्कों के योग की गणना करने के लिए, प्रिमिटिव रिकर्सन ऑपरेटर का उपयोग करके प्राप्त किया जा सकता है <math>\rho</math>. इसके लिए, प्रसिद्ध समीकरण
 :<math>\begin{array}{rcll}
 +y & = & y & \text{ and} \\
 S(x)+y & = & S(x+y) & . \\
 \end{array}</math>
-प्रिमिटिव रिकर्सिव फंक्शन टर्मिनोलॉजी में रीफ़्रेश किया गया है: की परिभाषा में <math>\rho(g,h)</math>, पहला समीकरण चुनने का सुझाव देता है <math>g = P_1^1</math> प्राप्त करने के लिए <math>Add(0,y) = g(y) = y</math>; दूसरा समीकरण चुनने का सुझाव देता है <math>h = S \circ P_2^3</math> प्राप्त करने के लिए <math>Add(S(x),y) = h(x,Add(x,y),y) = (S \circ P_2^3)(x,Add(x,y),y) = S(Add(x,y))</math>. इसलिए, अतिरिक्त फ़ंक्शन को इस रूप में परिभाषित किया जा सकता है <math>Add = \rho(P_1^1,S \circ P_2^3)</math>. गणना उदाहरण के रूप में,
+"मौलिक पुनरावर्ती फलन शब्दावली में पुनर्प्रकाशित" हैं: की परिभाषा में <math>\rho(g,h)</math>, पहला समीकरण चुनने का सुझाव देता है <math>g = P_1^1</math> प्राप्त करने के लिए <math>Add(0,y) = g(y) = y</math>; दूसरा समीकरण चुनने का सुझाव देता है <math>h = S \circ P_2^3</math> प्राप्त करने के लिए <math>Add(S(x),y) = h(x,Add(x,y),y) = (S \circ P_2^3)(x,Add(x,y),y) = S(Add(x,y))</math>. इसलिए, अतिरिक्त फलन को इस रूप में परिभाषित किया जा सकता है <math>Add = \rho(P_1^1,S \circ P_2^3)</math>. गणना उदाहरण के रूप में,
 :<math>\begin{array}{lll}
 & Add(1,7) \\
@@ Line 69: / Line 71: @@
 = & 8 & \text{ by Def. } S . \\
 \end{array}</math>
 === दोहरीकरण ===
-दिया गया <math>Add</math>, 1-एरी फ़ंक्शन <math>Add \circ (P_1^1,P_1^1)</math> इसके तर्क को दोगुना करता है, <math>(Add \circ (P_1^1,P_1^1))(x) = Add(x,x) = x+x</math>.
+दिया गया <math>Add</math>, 1-एरी फलन <math>Add \circ (P_1^1,P_1^1)</math> इसके तर्क को दोगुना करता है, <math>(Add \circ (P_1^1,P_1^1))(x) = Add(x,x) = x+x</math>.
 === गुणन ===
@@ Line 91: / Line 91: @@
 = & Mul(x,y)+y & \text{ by property of } Add . \\
 \end{array}</math>
 === पूर्ववर्ती ===
-पूर्ववर्ती कार्य उत्तराधिकारी कार्य के विपरीत कार्य करता है और नियमों द्वारा पुनरावर्ती रूप से परिभाषित किया जाता है <math>Pred(0) = 0</math> और <math>Pred(S(n)) = n</math>. एक आदिम पुनरावर्ती परिभाषा है <math>Pred = \rho(C_0^0, P_1^2)</math>. गणना उदाहरण के रूप में,
+पूर्ववर्ती कार्य उत्तराधिकारी कार्य के विपरीत कार्य करता है और नियमों द्वारा पुनरावर्ती रूप से परिभाषित किया जाता है <math>Pred(0) = 0</math> और <math>Pred(S(n)) = n</math>. प्राचीन पुनरावर्ती परिभाषा है <math>Pred = \rho(C_0^0, P_1^2)</math>. गणना उदाहरण के रूप में,
 :<math>\begin{array}{lll}
 & Pred(8) \\
@@ Line 102: / Line 100: @@
 = & 7 & \text{ by Def. } P_1^2 . \\
 \end{array}</math>
 === कटा हुआ घटाव ===
-सीमित घटाव फ़ंक्शन (जिसे [[monus]] भी कहा जाता है, और निरूपित किया जाता है<math>\stackrel.-</math>) पूर्ववर्ती कार्य से निश्चित है। यह समीकरणों को संतुष्ट करता है
+सीमित घटाव फलन (जिसे [[monus|मोनस]] भी कहा जाता है, और निरूपित किया जाता है<math>\stackrel.-</math>) पूर्ववर्ती कार्य से निश्चित है। यह समीकरणों को संतुष्ट करता है
 :<math>\begin{array}{rcll}
 y \stackrel.- 0 & = & y & \text{and} \\
 y \stackrel.- S(x) & = & Pred(y \stackrel.- x) & . \\
 \end{array}</math>
-चूंकि पुनरावर्तन दूसरे तर्क पर चलता है, हम उलटे घटाव की एक आदिम पुनरावर्ती परिभाषा के साथ शुरू करते हैं, <math>RSub(y,x) = x \stackrel.- y</math>. इसका पुनरावर्तन तब पहले तर्क पर चलता है, इसलिए इसकी आदिम पुनरावर्ती परिभाषा प्राप्त की जा सकती है, इसके अतिरिक्त, जैसा <math>RSub = \rho(P_1^1, Pred \circ P_2^3)</math>. उल्टे तर्क क्रम से छुटकारा पाने के लिए, फिर परिभाषित करें <math>Sub = RSub \circ (P_2^2,P_1^2)</math>. गणना उदाहरण के रूप में,
+चूंकि पुनरावर्तन दूसरे तर्क पर चलता है, हम उलटे घटाव की एक प्राचीन पुनरावर्ती परिभाषा के साथ प्रारंभ करते हैं, <math>RSub(y,x) = x \stackrel.- y</math>. इसका पुनरावर्तन तब पहले तर्क पर चलता है, इसलिए इसकी प्राचीन पुनरावर्ती परिभाषा प्राप्त की जा सकती है, इसके अतिरिक्त, जैसा <math>RSub = \rho(P_1^1, Pred \circ P_2^3)</math>. उल्टे तर्क क्रम से छुटकारा पाने के लिए, फिर परिभाषित करें <math>Sub = RSub \circ (P_2^2,P_1^2)</math>. गणना उदाहरण के रूप में,
 :<math>\begin{array}{lll}
 & Sub(8,1) \\
@@ Line 124: / Line 120: @@
 = & 7 & \text{ by property of } Pred . \\
 \end{array}</math>
+=== विधेय को संख्यात्मक कार्यों में परिवर्तित करना ===
+कुछ सेटिंग्स में मौलिक पुनरावर्ती फलनों पर विचार करना स्वाभाविक है,जो इनपुट के रूप में लेते हैं जो सत्य मानों के साथ संख्याओं को मिलाते हैं (जो कि सत्य के लिए t है और असत्य के लिए f है), या जो आउटपुट के रूप में सत्य मान उत्पन्न करते हैं। <ref>Kleene [1952 pp.&nbsp;226–227]</ref> इसे किसी निश्चित विधि से संख्याओं के साथ सत्य मानों की पहचान करके पूरा किया जा सकता है। उदाहरण के लिए, संख्या 1 के साथ सत्य मान t और संख्या 0 के साथ सत्य मान f की पहचान करना आम है। एक बार यह पहचान हो जाने के बाद, सेट A का विशिष्ट कार्य, जो हमेशा 1 या 0 देता है, हो सकता है एक विधेय के रूप में देखा जाता है जो बताता है कि सेट ए में कोई संख्या है या नहीं। संख्यात्मक कार्यों के साथ विधेय की ऐसी पहचान इस लेख के शेष भाग के लिए मानी जाएगी।
-=== विधेय को संख्यात्मक कार्यों में परिवर्तित करना ===
+'''विधेय "शून्य है"'''
-कुछ सेटिंग्स में आदिम पुनरावर्ती कार्यों पर विचार करना स्वाभाविक है जो इनपुट टुपल्स के रूप में लेते हैं जो सत्य मानों के साथ संख्याओं को मिलाते हैं (जो कि सत्य के लिए t है और गलत के लिए f है), या जो आउटपुट के रूप में सत्य मान उत्पन्न करते हैं।<ref>Kleene [1952 pp.&nbsp;226–227]</ref> इसे किसी निश्चित तरीके से संख्याओं के साथ सत्य मानों की पहचान करके पूरा किया जा सकता है। उदाहरण के लिए, संख्या 1 के साथ सत्य मान t और संख्या 0 के साथ सत्य मान f की पहचान करना आम है। एक बार यह पहचान हो जाने के बाद, सेट A का सूचक कार्य, जो हमेशा 1 या 0 देता है, हो सकता है एक विधेय के रूप में देखा जाता है जो बताता है कि सेट ए में कोई संख्या है या नहीं। संख्यात्मक कार्यों के साथ विधेय की ऐसी पहचान इस लेख के शेष भाग के लिए मानी जाएगी।
-=== विधेय शून्य === है
+प्राचीन पुनरावर्ती विधेय के लिए उदाहरण के रूप में, 1-एरी फलन <math>IsZero</math> इस प्रकार परिभाषित किया जाएगा <math>IsZero(x) = 1</math> यदि <math>x = 0</math>, और
-आदिम पुनरावर्ती विधेय के लिए एक उदाहरण के रूप में, 1-एरी फ़ंक्शन <math>IsZero</math> इस प्रकार परिभाषित किया जाएगा <math>IsZero(x) = 1</math> अगर <math>x = 0</math>, और
+<math>IsZero(x) = 0</math>, अन्यथा। इसे परिभाषित करके प्राप्त किया जा सकता है <math>IsZero = \rho(C_1^0,C_0^2)</math>. तब, <math>IsZero(0) = \rho(C_1^0,C_0^2)(0) = C_1^0(0) = 1</math> और उदा. <math>IsZero(8) = \rho(C_1^0,C_0^2)(S(7)) = C_0^2(7,IsZero(7)) = 0</math>.
- <math>IsZero(x) = 0</math>, अन्यथा। इसे परिभाषित करके प्राप्त किया जा सकता है <math>IsZero = \rho(C_1^0,C_0^2)</math>. तब, <math>IsZero(0) = \rho(C_1^0,C_0^2)(0) = C_1^0(0) = 1</math> और उदा. <math>IsZero(8) = \rho(C_1^0,C_0^2)(S(7)) = C_0^2(7,IsZero(7)) = 0</math>.
 === विधेय कम या बराबर ===
-संपत्ति का उपयोग करना <math>x \leq y \iff x \stackrel.- y = 0</math>, 2-एरी फ़ंक्शन <math>Leq</math> द्वारा परिभाषित किया जा सकता है <math>Leq = IsZero \circ Sub</math>. तब <math>Leq(x,y) = 1</math> अगर <math>x \leq y</math>, और <math>Leq(x,y) = 0</math>, अन्यथा। गणना उदाहरण के रूप में,
+संपत्ति का उपयोग करना <math>x \leq y \iff x \stackrel.- y = 0</math>, 2-एरी फलन <math>Leq</math> द्वारा परिभाषित किया जा सकता है <math>Leq = IsZero \circ Sub</math>. तब <math>Leq(x,y) = 1</math> यदि <math>x \leq y</math>, और <math>Leq(x,y) = 0</math>, अन्यथा। गणना उदाहरण के रूप में,
 :<math>\begin{array}{lll}
 & Leq(8,3) \\
@@ Line 144: / Line 139: @@
 = & 0  & \text{ by property of } IsZero \\
 \end{array}</math>
 === विधेय ग्रेटर या बराबर ===
-एक बार की परिभाषा <math>Leq</math> प्राप्त होता है, तो विलोम विधेय को इस प्रकार परिभाषित किया जा सकता है <math>Geq = Leq \circ (P_2^2,P_1^2)</math>. तब, <math>Geq(x,y) = Leq(y,x)</math> सत्य है (अधिक सटीक: मान 1 है) यदि, और केवल यदि, <math>x \geq y</math>.
+एक बार की परिभाषा <math>Leq</math> प्राप्त होता है, तो विलोम विधेय को इस प्रकार परिभाषित किया जा सकता है <math>Geq = Leq \circ (P_2^2,P_1^2)</math>. तब, <math>Geq(x,y) = Leq(y,x)</math> सत्य है (अधिक त्रुटिहीन: मान 1 है) यदि, और केवल यदि, <math>x \geq y</math>.
-=== अगर-तो-और ===
+=== यदि-तो-और ===
 प्रोग्रामिंग भाषाओं से ज्ञात 3-एरी if-then-else ऑपरेटर द्वारा परिभाषित किया जा सकता है <math>\textit{If} = \rho(P_2^2,P_3^4)</math>. फिर, मनमानी के लिए <math>x</math>,
@@ Line 166: / Line 159: @@
 = & z & \text{ by Def. } P_2^2 . \\
 \end{array}</math>.
-वह है, <math>\textit{If}(x,y,z)</math> तत्कालीन भाग देता है, <math>y</math>, अगर-भाग, <math>x</math>, सत्य है, और अन्य भाग, <math>z</math>, अन्यथा।
+वह है, <math>\textit{If}(x,y,z)</math> तत्कालीन भाग देता है, <math>y</math>, यदि-भाग, <math>x</math>, सत्य है, और अन्य भाग, <math>z</math>, अन्यथा।
 === जंक्शन ===
-पर आधारित <math>\textit{If}</math> कार्य, तार्किक जंक्शनों को परिभाषित करना आसान है। उदाहरण के लिए परिभाषित करना <math>And = \textit{If} \circ (P_1^2,P_2^2,C_0^2)</math>, एक प्राप्त करता है <math>And(x,y) = \textit{If}(x,y,0)</math>, वह है, <math>And(x,y)</math> सच है अगर, और केवल अगर, दोनों <math>x</math> और <math>y</math> सत्य हैं ([[तार्किक संयोजन]] <math>x</math> और <math>y</math>).
+पर आधारित <math>\textit{If}</math> कार्य, तार्किक जंक्शनों को परिभाषित करना आसान है। उदाहरण के लिए परिभाषित करना <math>And = \textit{If} \circ (P_1^2,P_2^2,C_0^2)</math>, एक प्राप्त करता है <math>And(x,y) = \textit{If}(x,y,0)</math>, वह है, <math>And(x,y)</math> सच है यदि, और केवल यदि, दोनों <math>x</math> और <math>y</math> सत्य हैं ([[तार्किक संयोजन]] <math>x</math> और <math>y</math>).
 इसी प्रकार, <math>Or = \textit{If} \circ (P_1^2,C_1^2,P_2^2)</math> और <math>Not = \textit{If} \circ (P_1^1,C_0^1,C_1^1)</math> वियोजन और निषेध की उपयुक्त परिभाषाओं की ओर ले जाते हैं: <math>Or(x,y) = \textit{If}(x,1,y)</math> और <math>Not(x) = \textit{If}(x,0,1)</math>.
@@ Line 176: / Line 169: @@
 === समानता विधेय ===
-उपरोक्त कार्यों का उपयोग करना <math>Leq</math>, <math>Geq</math> और <math>And</math>, मानहानि <math>Eq = And \circ (Leq, Geq)</math> समानता विधेय को लागू करता है। वास्तव में, <math>Eq(x,y) = And( Leq(x,y) , Geq(x,y) )</math> सच है अगर, और केवल अगर, <math>x</math> के बराबर होती है <math>y</math>.
+उपरोक्त कार्यों का उपयोग करना <math>Leq</math>, <math>Geq</math> और <math>And</math>, मानहानि <math>Eq = And \circ (Leq, Geq)</math> समानता विधेय को लागू करता है। वास्तव में, <math>Eq(x,y) = And( Leq(x,y) , Geq(x,y) )</math> सच है यदि, और केवल यदि, <math>x</math> के बराबर होती है <math>y</math>.
 इसी प्रकार, परिभाषा <math>Lt = Not \circ Geq</math> कम-से-कम विधेय को लागू करता है, और <math>Gt = Not \circ Leq</math> से अधिक लागू करता है।
@@ Line 182: / Line 175: @@
 === प्राकृत संख्याओं पर अन्य संक्रियाएं ===
-[[घातांक]] और [[प्रारंभिक परीक्षण]] आदिम पुनरावर्ती हैं। आदिम पुनरावर्ती कार्यों e, f, g, और h को देखते हुए, एक फ़ंक्शन जो e≤f होने पर g का मान लौटाता है और अन्यथा h का मान आदिम पुनरावर्ती होता है।
+[[घातांक]] और [[प्रारंभिक परीक्षण]] प्राचीन पुनरावर्ती हैं। मौलिक पुनरावर्ती फलनों e, f, g, और h को देखते हुए, एक फलन जो e≤f होने पर g का मान लौटाता है और अन्यथा h का मान प्राचीन पुनरावर्ती होता है।
 === पूर्णांकों और परिमेय संख्याओं पर संक्रियाएं ===
-गोडेल नंबरिंग का उपयोग करके, आदिम पुनरावर्ती कार्यों को पूर्णांक और परिमेय संख्याओं जैसे अन्य वस्तुओं पर संचालित करने के लिए बढ़ाया जा सकता है। यदि पूर्णांकों को गोडेल संख्याओं द्वारा एक मानक तरीके से एन्कोड किया जाता है, तो जोड़, घटाव और गुणा सहित अंकगणितीय संक्रियाएं सभी आदिम पुनरावर्ती हैं। इसी तरह, यदि परिमेय गोडेल संख्याओं द्वारा दर्शाए जाते हैं तो फ़ील्ड (गणित) संक्रियाएँ सभी आदिम पुनरावर्ती हैं।
+गोडेल नंबरिंग का उपयोग करके, मौलिक पुनरावर्ती फलनों को पूर्णांक और परिमेय संख्याओं जैसे अन्य वस्तुओं पर संचालित करने के लिए बढ़ाया जा सकता है। यदि पूर्णांकों को गोडेल संख्याओं द्वारा मानक विधि से एन्कोड किया जाता है, तो जोड़, घटाव और गुणा सहित अंकगणितीय संक्रियाएं सभी प्राचीन पुनरावर्ती हैं। इसी तरह, यदि परिमेय गोडेल संख्याओं द्वारा दर्शाए जाते हैं तो फ़ील्ड (गणित) संक्रियाएँ सभी प्राचीन पुनरावर्ती हैं।
-=== कुछ सामान्य आदिम पुनरावर्ती कार्य ===
+=== कुछ सामान्य मौलिक पुनरावर्ती फलन ===
-{{cleanup|section|reason=Remove functions and explanations that appear above|date=November 2021}}
+: निम्नलिखित उदाहरण और परिभाषाएँ क्लेन (1952) पीपी. 223–231 से हैं - कई सबूतों के साथ दिखाई देते हैं। बूलोस-बर्गेस-जेफरी 2002 पीपी। 63-70 में अधिकांश समान नामों के साथ, या तो प्रमाण के रूप में या उदाहरण के रूप में दिखाई देते हैं; वे त्रुटिहीन व्युत्पत्ति के आधार पर लघुगणक lo(x, y) या lg(x, y) जोड़ते हैं।
-: निम्नलिखित उदाहरण और परिभाषाएं क्लेन (1952) पीपी 223-231 से हैं - कई प्रमाण के साथ दिखाई देते हैं। बूलोस-बर्गेस-जेफरी 2002 पीपी. 63-70 में अधिकांश समान नामों के साथ, या तो प्रमाण के रूप में या उदाहरण के रूप में दिखाई देते हैं; वे सटीक व्युत्पत्ति के आधार पर लघुगणक lo(x, y) या lg(x, y) जोड़ते हैं।
 निम्नलिखित में हम देखते हैं कि आदिम पुनरावर्ती कार्य चार प्रकार के हो सकते हैं:
-# संक्षेप में कार्य: संख्या-सैद्धांतिक कार्य {0, 1, 2, ...} से {0, 1, 2, ...} तक,
+# संक्षेप में कार्य: "संख्या-सैद्धांतिक कार्य" {0, 1, 2, ...} से {0, 1, 2, ...} तक,
-# विधेय: {0, 1, 2, ...} से सत्य मान {t =true, f =false},
+# विधेय: {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 सत्य है।
+# कार्यों का प्रतिनिधित्व: सत्य मान {टी, एफ} से {0, 1, 2, ...}। कई बार एक विधेय को विधेय के आउटपुट { t, f } को { 0, 1 } में परिवर्तित करने के लिए एक प्रतिनिधित्व फलन की आवश्यकता होती है (~sg() परिभाषित के साथ "t" से "0" और "f" से "1" के क्रम पर ध्यान दें नीचे)। परिभाषा के अनुसार एक फलन φ(x) विधेय P(x) का एक "प्रतिनिधित्व फलन" है यदि φ केवल मान 0 और 1 लेता है और 0 उत्पन्न करता है जब P सत्य है"।
-निम्नलिखित में चिह्न ' , उदा. a', आदिम चिह्न है जिसका अर्थ उत्तराधिकारी है, जिसे आमतौर पर +1 के रूप में माना जाता है, उदा। एक +1 =<sub>def</sub> ए'। कार्य 16-20 और #G आदिम पुनरावर्ती विधेय को गोडेल संख्या के रूप में व्यक्त उनके अंकगणितीय रूप में परिवर्तित करने और उनसे निकालने के संबंध में विशेष रुचि रखते हैं।
+निम्नलिखित में चिह्न " ' ", उदा. a' आदिम चिह्न है जिसका अर्थ है "का उत्तराधिकारी", सामान्यतः " +1", के रूप में माना जाता है, उदा a +1 = डीईएफ़ a'। कार्यों 16-20 और #G आदिम पुनरावर्ती विधेय को परिवर्तित करने और उन्हें निकालने के संबंध में विशेष रुचि रखते हैं, उनके "अंकगणितीय" रूप को गोडेल संख्या के रूप में व्यक्त किया गया है।
-: # जोड़: ए + बी
+:* जोड़: a+b
-:# गुणन: a×b
+:* गुणन: a×b
-: # घातांक: ए<sup>ख</सुप>
-: # फैक्टोरियल ए! : 0! = 1, ए'! = ए! × ए'
-: # पूर्व (ए): (पूर्ववर्ती या कमी): यदि ए> 0 तो ए -1 और 0
-:# उचित घटाव a ∸ b: यदि a ≥ b तो a-b और 0
-: # न्यूनतम (ए<sub>1</sub>, ... ए<sub>n</sub>)
-: # अधिकतम (ए<sub>1</sub>, ... ए<sub>n</sub>)
-:#पूर्ण अंतर: | ए-बी | =<sub>def</sub> (ए ∸ बी) + (बी ∸ ए)
-:# ~sg(a): NOT[signum(a)]: अगर a=0 तो 1 और 0
-: # एसजी (ए): साइनम (ए): यदि ए = 0 तो 0 और 1
-:#ए | b: (a b को विभाजित करता है): यदि b=k×a कुछ k के लिए तो 0 और 1
-:# Remainder(a, b): बचे हुए अगर b समान रूप से विभाजित नहीं करता है। एमओडी (ए, बी) भी कहा जाता है
-:# ए = बी: एसजी | ए - बी | (क्लीन की प्रथा को 0 से सत्य और 1 से असत्य का प्रतिनिधित्व करना था; वर्तमान में, विशेष रूप से कंप्यूटरों में, सबसे आम सम्मेलन रिवर्स है, अर्थात् 1 से सत्य और 0 से गलत का प्रतिनिधित्व करने के लिए, जो यहाँ और ~sg में sg को बदलने की मात्रा है। अगला आइटम)
-:# a < b: sg( a' ∸ b )
-:# Pr(a): a एक अभाज्य संख्या है Pr(a) =<sub>def</sub> a>1 और नहीं (मौजूद c)<sub>1<c<a</sub> [सी|ए]
-:# पी<sub>i</sub>: i+1-st अभाज्य संख्या
-:# (ए)<sub>i</sub>: पी के प्रतिपादक<sub>i</sub> a में: अद्वितीय x ऐसा है कि p<sub>i</sub><sup>x</sup>|a और NOT(p<sub>i</sub><sup>एक्स'</sup>|ए)
-: # एलएच (ए): लंबाई या गायब न होने वाले घातांक की संख्या
-: # लो (ए, बी): (आधार बी के लघुगणक): यदि ए, बी> 1 तो सबसे बड़ा एक्स ऐसा है कि बी<sup>एक्स </सुप> | एक अन्य 0
-: निम्नलिखित में संक्षिप्त रूप 'x' =<sub>def</sub> एक्स<sub>1</sub>, ... एक्स<sub>n</sub>; अर्थ की आवश्यकता होने पर सबस्क्रिप्ट लागू किया जा सकता है।
+** घातांक: a<sup>b</sup>
+:* क्रमगुणित ए! :0! = 1, a'! = a!×a'
+:* पूर्ववर्ती (a): (पूर्ववर्ती या कमी): यदि a > 0 तो a-1 और 0
+:* उचित घटाव a ∸ b: यदि a ≥ b तो a-b और 0
+:* न्यूनतम (a<sub>1</sub>, ... a<sub>n</sub>)
+:* अधिकतम (a<sub>1</sub>, ... a<sub>n</sub>)
+:* पूर्ण अंतर: | a-b | =<sub>def</sub> (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) =<sub>def</sub> a>1 & NOT(उपस्थित c)<sub>1<c<a</sub> [ c|a ]
+:#p<sub>i</sub>: i+1-st अभाज्य संख्या
+:#(a)<sub>i</sub>: a में pi का प्रतिपादक: अद्वितीय x ऐसा है कि p<sub>i</sub><sup>x</sup>|a & NOT(p<sub>i</sub><sup>x'</sup>|a)
+:#lh(a): "लंबाई" या गैर-लुप्त होने वाले xपोनेंट्स की संख्या
+:#lo(a, b): (आधार b का लघुगणक): यदि a, b > 1 तो सबसे बड़ा x ऐसा है कि b<sup>x</sup> | a अन्य 0
-* #A: एक फ़ंक्शन φ स्पष्ट रूप से फ़ंक्शन Ψ और स्थिरांक q से निश्चित है<sub>1</sub>, ... क्यू<sub>n</sub> Ψ में आदिम पुनरावर्ती है।
+: निम्नलिखित में संक्षिप्त रूप 'x' =<sub>def</sub> x<sub>1</sub>, ... x<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>, क्यू।
+* #A: एक फलन φ स्पष्ट रूप से फलन Ψ और स्थिरांक q से निश्चित है q<sub>1</sub>, ... q<sub>n</sub> Ψ में प्राचीन पुनरावर्ती है।
-* #D: निम्नलिखित विधेय Q और R में आदिम पुनरावर्ती हैं:
+* #B: परिमित योग Σ<sub>y<z</sub> ψ(x, y) और उत्पाद Π<sub>y<z</sub>ψ(x, y) ψ में प्राचीन पुनरावर्ती हैं।
+* #C: एक ''विधेय'' पी कार्यों χ प्रतिस्थापन द्वारा प्राप्त कियाχ<sub>1</sub>,..., χ<sub>m</sub> एक विधेय के संबंधित चर के लिए Q χ में प्राचीन पुनरावर्ती है χ<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 विधेय में आदिम पुनरावर्ती हैं:
+* #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: स्थितियों द्वारा परिभाषा: इस प्रकार परिभाषित फ़ंक्शन, जहां Q1, ..., 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>(एक्स) सच है,
+::* φ<sub>1</sub>(x) यदि Q<sub>1</sub> (x) सच है,
 ::* . . . . . . . . . . . . . . . . . . .
-::* φ<sub>m</sub>(एक्स) अगर क्यू<sub>m</sub>(एक्स) सच है
+::* φ<sub>m</sub>(x) यदि Q<sub>m</sub>(x) सच है
-::* φ<sub>m+1</sub>(एक्स) अन्यथा
+::* φ<sub>m+1</sub>(x) अन्यथा
 * #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>, ... x<sub>n</sub> ), x<sub>2</sub>, ... x<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, +, *, और ≤ के अलावा है। इस प्रकार आदिम पुनरावर्ती कार्यों को परिभाषित करने के लिए गोडेल द्वारा निम्नलिखित चाल का उपयोग करना होगा।
+प्रथम-क्रम तर्क में | प्रथम-क्रम पीआनो अंकगणित में असीमित रूप से कई चर (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>
-और जी के बराबर, पहले से ही परिभाषित किया जा रहा है, वास्तव में कुछ अन्य पहले से परिभाषित सूत्र के लिए आशुलिपि है (जैसा कि β है, जिसका सूत्र गोडेल का β फ़ंक्शन दिया गया है)।
+और जी के बराबर, पहले से ही परिभाषित किया जा रहा है, वास्तव में कुछ अन्य पहले से परिभाषित सूत्र के लिए आशुलिपि है (जैसा कि β है, जिसका सूत्र गोडेल का β फलन दिया गया है)।
-किसी भी k-ary आदिम पुनरावर्तन समारोह का सामान्यीकरण तुच्छ है।
+किसी भी k-ary प्रारंभिक पुनरावर्तन फलन का सामान्यीकरण तुच्छ है।
 == पुनरावर्ती कार्यों से संबंध ==
-[[आंशिक पुनरावर्ती कार्य]]ों के व्यापक वर्ग को [[ऑपरेटर में]] की शुरुआत करके परिभाषित किया गया है। इस ऑपरेटर के उपयोग के परिणामस्वरूप आंशिक फ़ंक्शन हो सकता है, अर्थात, प्रत्येक तर्क के लिए अधिकतम एक मान के साथ संबंध, लेकिन किसी भी तर्क के लिए कोई मान आवश्यक नहीं है (फ़ंक्शन का डोमेन देखें)। एक समतुल्य परिभाषा बताती है कि एक आंशिक पुनरावर्ती कार्य वह है जिसे [[ट्यूरिंग मशीन]] द्वारा गणना की जा सकती है। टोटल रिकर्सिव फंक्शन एक आंशिक रिकर्सिव फंक्शन है जिसे हर इनपुट के लिए परिभाषित किया गया है।
+[[आंशिक पुनरावर्ती कार्य|आंशिक पुनरावर्ती कार्यों]] के व्यापक वर्ग को असीमित खोज [[ऑपरेटर में|ऑपरेटर]] की प्रारंभ करके परिभाषित किया गया है। इस ऑपरेटर के उपयोग के परिणामस्वरूप आंशिक फलन हो सकता है, अर्थात, प्रत्येक तर्क के लिए अधिकतम एक मान के साथ संबंध, लेकिन किसी भी तर्क के लिए कोई मान आवश्यक नहीं है (डोमेन देखें)। समतुल्य परिभाषा बताती है कि एक आंशिक पुनरावर्ती कार्य वह है जिसे [[ट्यूरिंग मशीन]] द्वारा गणना की जा सकती है। टोटल रिकर्सिव फंक्शन एक आंशिक रिकर्सिव फंक्शन है जिसे हर इनपुट के लिए परिभाषित किया गया है।
-प्रत्येक आदिम पुनरावर्ती कार्य कुल पुनरावर्ती है, लेकिन सभी कुल पुनरावर्ती कार्य आदिम पुनरावर्ती नहीं हैं। [[एकरमैन समारोह]] ए (एम, एन) कुल पुनरावर्ती फ़ंक्शन (वास्तव में, सिद्ध करने योग्य कुल) का एक प्रसिद्ध उदाहरण है, जो आदिम पुनरावर्ती नहीं है। एकरमैन फ़ंक्शन का उपयोग करके कुल पुनरावर्ती कार्यों के सबसेट के रूप में आदिम पुनरावर्ती कार्यों का एक लक्षण वर्णन है। यह लक्षण वर्णन बताता है कि एक फ़ंक्शन आदिम पुनरावर्ती है यदि और केवल यदि कोई प्राकृतिक संख्या 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>
+प्रत्येक मौलिक पुनरावर्ती फलन कुल पुनरावर्ती है, लेकिन सभी कुल पुनरावर्ती कार्य प्राचीन पुनरावर्ती नहीं हैं। [[एकरमैन समारोह|एकरमैन फलन]] A(''m'',''n'') कुल पुनरावर्ती फलन (वास्तव में, सिद्ध करने योग्य कुल) का एक प्रसिद्ध उदाहरण है, जो प्राचीन पुनरावर्ती नहीं है। एकरमैन फलन का उपयोग करके कुल पुनरावर्ती कार्यों के सबसेट के रूप में मौलिक पुनरावर्ती फलनों का लक्षण वर्णन है। यह लक्षण वर्णन बताता है कि एक फलन प्राचीन पुनरावर्ती है, यदि कोई प्राकृतिक संख्या 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>
-आदिम पुनरावर्ती कार्यों की एक महत्वपूर्ण संपत्ति यह है कि वे सभी कुल पुनरावर्ती कार्यों के सेट का पुनरावर्ती रूप से गणना करने योग्य उपसमुच्चय हैं (जो स्वयं पुनरावर्ती गणना योग्य नहीं है)। इसका मतलब यह है कि एक एकल संगणनीय कार्य f(m,n) है जो आदिम पुनरावर्ती कार्यों की गणना करता है, अर्थात्:
-* प्रत्येक आदिम पुनरावर्ती क्रिया g के लिए, एक m ऐसा है कि g(n) = f(m,n) सभी n के लिए, और
-* प्रत्येक एम के लिए, फ़ंक्शन एच (एन) = एफ (एम, एन) आदिम पुनरावर्ती है।
-च को आदिम पुनरावर्ती कार्यों को बनाने के सभी संभावित तरीकों को दोहराकर स्पष्ट रूप से बनाया जा सकता है। इस प्रकार, यह कुल साबित होता है। एक [[विकर्ण लेम्मा]] तर्क का उपयोग यह दिखाने के लिए कर सकता है कि f अपने आप में पुनरावर्ती आदिम नहीं है: यदि ऐसा होता, तो h(n) = f(n,n)+1 होता। लेकिन अगर यह कुछ आदिम पुनरावर्ती फ़ंक्शन के बराबर है, तो एक एम ऐसा है कि एच (एन) = एफ (एम, एन) सभी एन के लिए, और फिर एच (एम) = एफ (एम, एम), विरोधाभास के लिए अग्रणी।
-हालाँकि, आदिम पुनरावर्ती कार्यों का सेट सभी कुल पुनरावर्ती कार्यों के सेट का सबसे बड़ा पुनरावर्ती गणनीय उपसमुच्चय नहीं है। उदाहरण के लिए, साबित कुल कार्यों का सेट (पीनो अंकगणित में) भी पुनरावर्ती गणना योग्य है, क्योंकि सिद्धांत के सभी सबूतों की गणना कर सकते हैं। जबकि सभी आदिम पुनरावर्ती कार्य सिद्ध रूप से कुल हैं, इसका विलोम सत्य नहीं है।
+मौलिक पुनरावर्ती फलनों की महत्वपूर्ण संपत्ति यह है कि वे सभी कुल पुनरावर्ती कार्यों के सेट का पुनरावर्ती रूप से गणना करने योग्य उपसमुच्चय हैं (जो स्वयं पुनरावर्ती गणना योग्य नहीं है)। इसका मतलब यह है कि एक एकल संगणनीय कार्य ''f''(''m'',''n'') है जो मौलिक पुनरावर्ती फलनों की गणना करता है, अर्थात्:
+* प्रत्येक प्राचीन पुनरावर्ती क्रिया g के लिए, एक m ऐसा है कि g(n) = f(m,n) सभी n के लिए, और
+* प्रत्येक एम के लिए, फलन ''h''(''n'') = ''f''(''m'',''n'') प्राचीन पुनरावर्ती है।
+''f'' को मौलिक पुनरावर्ती फलनों को बनाने के सभी संभावित तरीकों को दोहराकर स्पष्ट रूप से बनाया जा सकता है। इस प्रकार, यह कुल प्रमाण होता है। [[विकर्ण लेम्मा]] तर्क का उपयोग यह दिखाने के लिए कर सकता है कि f अपने आप में पुनरावर्ती प्राचीन नहीं है: यदि ऐसा होता, तो h(n) = f(n,n)+1 होता। लेकिन यदि यह कुछ प्राचीन पुनरावर्ती फलन के बराबर है, तो एम ऐसा है कि h(n) = f(m,n) सभी एन के लिए, और फिर एच (एम) = एफ (एम, एम), विरोधाभास के लिए अग्रणी।
-== सीमाएं ==<!-- This section is linked from [[Primitive recursive function]] -->
+चूँकि, मौलिक पुनरावर्ती फलनों का सेट सभी कुल पुनरावर्ती कार्यों के सेट का सबसे बड़ा पुनरावर्ती गणनीय उपसमुच्चय नहीं है। उदाहरण के लिए, प्रमाण कुल कार्यों का सेट (पीनो अंकगणित में) भी पुनरावर्ती गणना योग्य है, क्योंकि सिद्धांत के सभी सबूतों की गणना कर सकते हैं। जबकि सभी मौलिक पुनरावर्ती फलन सिद्ध रूप से कुल हैं, इसका विलोम सत्य नहीं है।
-आदिम पुनरावर्ती कार्य हमारे अंतर्ज्ञान के साथ बहुत निकटता से मेल खाते हैं कि एक संगणनीय कार्य क्या होना चाहिए। निश्चित रूप से प्रारंभिक कार्य सहज रूप से संगणनीय हैं (उनकी बहुत सरलता में), और दो ऑपरेशन जिनके द्वारा कोई नया आदिम पुनरावर्ती कार्य बना सकता है, वे भी बहुत सीधे हैं। हालाँकि, आदिम पुनरावर्ती कार्यों के सेट में हर संभव कुल गणना योग्य कार्य शामिल नहीं है - इसे कैंटर के विकर्ण तर्क के एक संस्करण के साथ देखा जा सकता है। यह तर्क कुल संगणनीय कार्य प्रदान करता है जो आदिम पुनरावर्ती नहीं है। सबूत का एक स्केच इस प्रकार है:
-{{block indent|The primitive recursive functions of one argument (i.e., unary functions) can be [[Recursively enumerable set|computably enumerated]]. This enumeration uses the definitions of the primitive recursive functions (which are essentially just expressions with the composition and primitive recursion operations as operators and the basic primitive recursive functions as atoms), and can be assumed to contain every definition once, even though a same ''function'' will occur many times on the list (since many definitions define the same function; indeed simply composing by the [[identity function]] generates infinitely many definitions of any one primitive recursive function). This means that the {{mvar|''n''}}-th definition of a primitive recursive function in this enumeration can be effectively determined from {{mvar|''n''}}. Indeed if one uses some [[Gödel numbering]] to encode definitions as numbers, then this {{mvar|''n''}}-th definition in the list is computed by a primitive recursive function of {{mvar|''n''}}. Let {{math|''f''<sub>''n''</sub>}} denote the unary primitive recursive function given by this definition.
+== सीमाएं ==
+मौलिक पुनरावर्ती फलन हमारे अंतर्ज्ञान के साथ बहुत निकटता से मेल खाते हैं कि संगणनीय कार्य क्या होना चाहिए। निश्चित रूप से प्रारंभिक कार्य सहज रूप से संगणनीय हैं (उनकी बहुत सरलता में), और दो ऑपरेशन जिनके द्वारा कोई नया मौलिक पुनरावर्ती फलन बना सकता है, वे भी बहुत सीधे हैं। चूँकि, मौलिक पुनरावर्ती फलनों के सेट में हर संभव कुल गणना योग्य कार्य सम्मलित नहीं है - इसे कैंटर के विकर्ण तर्क के संस्करण के साथ देखा जा सकता है। यह तर्क कुल संगणनीय कार्य प्रदान करता है जो प्राचीन पुनरावर्ती नहीं है। सबूत का एक स्केच इस प्रकार है:
-Now define the "evaluator function" {{mvar|''ev''}} with two arguments, by {{math|''ev''(''i'',''j'') {{=}} ''f''<sub>''i''</sub>(''j'')}}. Clearly {{math|''ev''}} is total and computable, since one can effectively determine the definition of {{math|''f''<sub>''i''</sub>}}, and being a primitive recursive function {{math|''f''<sub>''i''</sub>}} is itself total and computable, so {{math|''f''<sub>''i''</sub>(''j'')}} is always defined and effectively computable. However a diagonal argument will show that the function {{mvar|''ev''}} of two arguments is not primitive recursive.
+{{block indent|तर्क के आदिम पुनरावर्ती कार्य (अर्थात, एकात्मक कार्य) [[पुनरावर्ती रूप से गणना करने योग्य सेट | संगणनीय रूप से गणना]] हो सकते हैं। यह गणन आदिम पुनरावर्ती कार्यों की परिभाषाओं का उपयोग करता है (जो अनिवार्य रूप से रचना और आदिम पुनरावर्ती संचालन के साथ ऑपरेटरों के रूप में और परमाणुओं के रूप में बुनियादी आदिम पुनरावर्ती कार्यों के साथ अभिव्यक्ति हैं), और यह माना जा सकता है कि हर परिभाषा एक बार, भले ही एक ही हो। 'फ़ंक्शन'' सूची में कई बार होगा (चूंकि कई परिभाषाएं एक ही फ़ंक्शन को परिभाषित करती हैं; वास्तव में केवल [[पहचान फ़ंक्शन]] द्वारा रचने से किसी एक आदिम पुनरावर्ती फ़ंक्शन की असीम रूप से कई परिभाषाएँ उत्पन्न होती हैं)। इसका अर्थ है कि{{mvar|''n''}}-thइस गणना में आदिम पुनरावर्ती फलन की परिभाषा प्रभावी रूप से  {{mvar|''n''}}. से निर्धारित की जा सकती है। वास्तव में यदि कोई [[गोडेल नंबरिंग]] का उपयोग संख्याओं के रूप में परिभाषाओं को सांकेतिक शब्दों में बदलने के लिए करता है, तो यह  {{mvar|''n''}}-thसूची में वें परिभाषा की गणना {{mvar|'' के आदिम पुनरावर्ती कार्य द्वारा की जाती है। एन''}}। माना  {{mvar|''n''}}. दर्शाता है {{math|''f''<sub>''n''</sub>}} इस परिभाषा द्वारा दिए गए यूनरी प्रिमिटिव रिकर्सिव फंक्शन को निरूपित करें।
+अब "मूल्यांकनकर्ता फ़ंक्शन" को परिभाषित करें {{mvar|''ev''}} दो तर्कों के साथ, द्वारा  {{math|''ev''(''i'',''j'') {{=}} ''f''<sub>''i''</sub>(''j'')}}.स्पष्ट रूप से {{math|''ev''}} कुल और संगणनीय है, क्योंकि कोई प्रभावी रूप से इसकी परिभाषा निर्धारित कर सकता है{{math|''f''<sub>''i''</sub>}}, और एक प्राचीन पुनरावर्ती कार्य किया जा रहा है{{math|''f''<sub>''i''</sub>}}स्वयं कुल और गणना योग्य है, इसलिए {{math|''f''<sub>''i''</sub>(''j'')}} हमेशा परिभाषित और प्रभावी ढंग से संगणनीय है। हालांकि एक विकर्ण तर्क दिखाएगा कि {{mvar|''ev''}} दो तर्कों का आदिम पुनरावर्ती नहीं है।
-Suppose {{mvar|''ev''}} were primitive recursive, then the unary function {{mvar|''g''}} defined by {{math|''g''(''i'') {{=}} S(''ev''(''i'',''i''))}} would also be primitive recursive, as it is defined by composition from the successor function and {{mvar|''ev''}}. But then {{mvar|''g''}} occurs in the enumeration, so there is some number {{mvar|''n''}} such that {{math|''g'' {{=}} ''f''<sub>''n''</sub>}}. But now {{math|''g''(''n'') {{=}} S(''ev''(''n'',''n'')) {{=}} S(''f''<sub>''n''</sub>(''n'')) {{=}} S(''g''(''n''))}} gives a contradiction.}}
+कल्पना करना {{mvar|''ev''}} आदिम पुनरावर्ती थे, फिर एकात्मक कार्य{{mvar|''g''}} द्वारा परिभाषित {{math|''g''(''i'') {{=}} S(''ev''(''i'',''i''))}} आदिम पुनरावर्ती भी होगा, क्योंकि यह उत्तराधिकारी समारोह से संरचना द्वारा परिभाषित किया गया है और {{mvar|''ev''}}.परन्तु फिर {{mvar|''g''}} गणना में होता है, इसलिए कुछ संख्या होती है {{mvar|''n''}} ऐसा है कि{{math|''g'' {{=}} ''f''<sub>''n''</sub>}}. पर अब{{math|''g''(''n'') {{=}} S(''ev''(''n'',''n'')) {{=}} S(''f''<sub>''n''</sub>(''n'')) {{=}} S(''g''(''n''))}}
-यह तर्क गणना योग्य (कुल) कार्यों के किसी भी वर्ग पर लागू किया जा सकता है जिसे इस तरह से गणना की जा सकती है, जैसा लेख मशीन में समझाया गया है जो हमेशा रुकता है। हालांकि ध्यान दें कि आंशिक संगणनीय कार्य (जिन्हें सभी तर्कों के लिए परिभाषित करने की आवश्यकता नहीं है) को स्पष्ट रूप से गणना की जा सकती है, उदाहरण के लिए ट्यूरिंग मशीन एन्कोडिंग की गणना करके।
+विरोधाभास देता है।}}
+यह तर्क गणना योग्य (कुल) कार्यों के किसी भी वर्ग पर लागू किया जा सकता है जिसे इस तरह से गणना की जा सकती है, जैसा लेख मशीन में समझाया गया है जो हमेशा रुकता है। चूँकि ध्यान दें कि आंशिक संगणनीय कार्य (जिन्हें सभी तर्कों के लिए परिभाषित करने की आवश्यकता नहीं है) को स्पष्ट रूप से गणना की जा सकती है, उदाहरण के लिए ट्यूरिंग मशीन एन्कोडिंग की गणना करके।
-कुल पुनरावर्ती लेकिन आदिम पुनरावर्ती कार्यों के अन्य उदाहरण ज्ञात नहीं हैं:
+कुल पुनरावर्ती लेकिन मौलिक पुनरावर्ती फलनों के अन्य उदाहरण ज्ञात नहीं हैं:
-*फ़ंक्शन जो m को एकरमैन फ़ंक्शन(m,m) में ले जाता है वह एक एकल कुल पुनरावर्ती फ़ंक्शन है जो आदिम पुनरावर्ती नहीं है।
+*फलन जो m को एकरमैन फलन(m,m) में ले जाता है वह एक एकल कुल पुनरावर्ती फलन है जो प्राचीन पुनरावर्ती नहीं है।
-*पेरिस-हैरिंगटन प्रमेय में कुल पुनरावर्ती कार्य शामिल है जो आदिम पुनरावर्ती नहीं है।
+*पेरिस-हैरिंगटन प्रमेय में कुल पुनरावर्ती कार्य सम्मलित है जो प्राचीन पुनरावर्ती नहीं है।
-* [[सूडान समारोह]]
+* [[सूडान समारोह|सूडान फलन]]
-* [[गुडस्टीन समारोह]]
+* [[गुडस्टीन समारोह|गुडस्टीन फलन]]
 == वेरिएंट ==
@@ Line 294: / Line 288: @@
 === लगातार कार्य ===
 के बजाय <math>C_n^k</math>,
-वैकल्पिक परिभाषाएँ केवल एक 0-एरी शून्य फ़ंक्शन का उपयोग करती हैं <math>C_0^0</math> एक आदिम कार्य के रूप में जो हमेशा शून्य लौटाता है, और शून्य कार्य, उत्तराधिकारी कार्य और संरचना ऑपरेटर से निरंतर कार्यों का निर्माण करता है।
+वैकल्पिक परिभाषाएँ केवल एक 0-एरी शून्य फलन का उपयोग करती हैं <math>C_0^0</math> एक प्राचीन कार्य के रूप में जो हमेशा शून्य लौटाता है, और शून्य कार्य, उत्तराधिकारी कार्य और संरचना ऑपरेटर से निरंतर कार्यों का निर्माण करता है।
-=== कमजोर आदिम पुनरावर्तन ===
+=== कमजोर प्रारंभिक पुनरावर्तन ===
--स्थान का पूर्ववर्ती कार्य आदिम पुनरावर्ती है, अनुभाग #Predecessor देखें। फिशर, फिशर और बेगेल {{sfn|Fischer|Fischer|Beigel|1989}} प्रत्यावर्तन नियम से अंतर्निहित पूर्ववर्ती को हटा दिया, इसे कमजोर नियम से बदल दिया
+-स्थान का पूर्ववर्ती कार्य प्राचीन पुनरावर्ती है, अनुभाग #Predecessor देखें। फिशर, फिशर और बेगेल {{sfn|Fischer|Fischer|Beigel|1989}} प्रत्यावर्तन नियम से अंतर्निहित पूर्ववर्ती को हटा दिया, इसे कमजोर नियम से बदल दिया
 :<math>
 \begin{array}{lcl}
@@ Line 304: / Line 298: @@
 \end{array}
 </math>
-उन्होंने साबित किया कि पूर्ववर्ती कार्य अभी भी परिभाषित किया जा सकता है, और इसलिए कमजोर आदिम पुनरावर्तन आदिम पुनरावर्ती कार्यों को भी परिभाषित करता है।
+उन्होंने प्रमाण किया कि पूर्ववर्ती कार्य अभी भी परिभाषित किया जा सकता है, और इसलिए कमजोर प्रारंभिक पुनरावर्तन मौलिक पुनरावर्ती फलनों को भी परिभाषित करता है।
 === पुनरावृत्ति कार्य ===
@@ Line 310: / Line 304: @@
 <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>
+पुनरावृत्त कार्यों के वर्ग को उसी तरह परिभाषित किया जाता है जैसे इस कमजोर नियम को छोड़कर मौलिक पुनरावर्ती फलनों के वर्ग को। इन्हें मौलिक पुनरावर्ती फलनों का उचित उपसमुच्चय माना जाता है।<ref>{{Cite document|last=M. Fischer, R. Fischer, R. Beigel|title=Primitive Recursion without Implicit Predecessor}}</ref>
+=== अतिरिक्त प्राचीन पुनरावर्ती रूप ===
-=== अतिरिक्त आदिम पुनरावर्ती रूप ===
+पुनरावर्तन के कुछ अतिरिक्त रूप भी उन कार्यों को परिभाषित करते हैं जो वास्तव में हैं
-पुनरावर्तन के कुछ अतिरिक्त रूप भी उन कार्यों को परिभाषित करते हैं जो वास्तव में हैं
+प्राचीन पुनरावर्ती इन रूपों में परिभाषाएँ खोजना आसान हो सकता है या
-आदिम पुनरावर्ती। इन रूपों में परिभाषाएँ खोजना आसान हो सकता है या
+पढ़ने या लिखने के लिए अधिक स्वाभाविक। [[कोर्स-ऑफ़-वैल्यू रिकर्सन]] मौलिक पुनरावर्ती फलनों को परिभाषित करता है। [[आपसी पुनरावर्तन]] के कुछ रूप मौलिक पुनरावर्ती फलनों को भी परिभाषित करते हैं।
-पढ़ने या लिखने के लिए अधिक स्वाभाविक। [[कोर्स-ऑफ़-वैल्यू रिकर्सन]] आदिम पुनरावर्ती कार्यों को परिभाषित करता है। [[आपसी पुनरावर्तन]] के कुछ रूप आदिम पुनरावर्ती कार्यों को भी परिभाषित करते हैं।
-LOOP (प्रोग्रामिंग लैंग्वेज) में जिन कार्यों को प्रोग्राम किया जा सकता है, वे वास्तव में आदिम पुनरावर्ती कार्य हैं। यह इन कार्यों की शक्ति का एक अलग लक्षण वर्णन करता है। [[ट्यूरिंग-पूर्ण भाषा]] की तुलना में LOOP भाषा की मुख्य सीमा यह है कि LOOP भाषा में लूप चलने से पहले प्रत्येक लूप चलने की संख्या निर्दिष्ट होती है।
+लूप (प्रोग्रामिंग लैंग्वेज) में जिन कार्यों को प्रोग्राम किया जा सकता है, वे वास्तव में मौलिक पुनरावर्ती फलन हैं। यह इन कार्यों की शक्ति का एक अलग लक्षण वर्णन करता है। [[ट्यूरिंग-पूर्ण भाषा]] की तुलना में लूप भाषा की मुख्य सीमा यह है कि लूप भाषा में लूप चलने से पहले प्रत्येक लूप चलने की संख्या निर्दिष्ट होती है।
 === कंप्यूटर भाषा परिभाषा ===
-आदिम पुनरावर्ती प्रोग्रामिंग भाषा का एक उदाहरण वह है जिसमें बुनियादी अंकगणितीय ऑपरेटर (जैसे + और -, या ADD और SUBTRACT), सशर्त और तुलना (IF-THEN, EQUALS, LESS-THAN), और परिबद्ध लूप, जैसे बुनियादी शामिल हैं लूप के लिए, जहां सभी लूपों के लिए ज्ञात या गणना योग्य ऊपरी सीमा होती है (FOR i FROM 1 TO n, लूप बॉडी द्वारा न तो i और न ही संशोधित किया जा सकता है)। अधिक सामान्यता की कोई नियंत्रण संरचना, जैसे कि लूप या IF-THEN प्लस [[GOTO]], आदिम पुनरावर्ती भाषा में स्वीकार नहीं की जाती है।
+प्राचीन पुनरावर्ती प्रोग्रामिंग भाषा का उदाहरण वह है जिसमें बुनियादी अंकगणितीय ऑपरेटर (जैसे + और -, या ADD और SUBTRACT), सशर्त और तुलना (IF-THEN, EQUALS, LESS-THAN), और परिबद्ध लूप, जैसे बुनियादी सम्मलित हैं लूप के लिए, जहां सभी लूपों के लिए ज्ञात या गणना योग्य ऊपरी सीमा होती है (FOR i FROM 1 TO n, लूप बॉडी द्वारा न तो i और न ही संशोधित किया जा सकता है)। अधिक सामान्यता की कोई नियंत्रण संरचना, जैसे कि लूप या IF-THEN प्लस [[GOTO]], प्राचीन पुनरावर्ती भाषा में स्वीकार नहीं की जाती है।
-LOOP (प्रोग्रामिंग लैंग्वेज), 1967 में अल्बर्ट आर. मेयर और डेनिस एम. रिची द्वारा पेश किया गया,<ref>{{cite conference
+लूप (प्रोग्रामिंग लैंग्वेज), 1967 में अल्बर्ट आर. मेयर और डेनिस एम. रिची द्वारा प्रस्तुत किया गया,<ref>{{cite conference
 | doi=10.1145/800196.806014
 | title=The complexity of loop programs
@@ Line 337: / Line 331: @@
 | year=1967
 | doi-access=free
-}}</ref> एक ऐसी भाषा है। इसकी कंप्यूटिंग शक्ति आदिम पुनरावर्ती कार्यों के साथ मेल खाती है। LOOP भाषा का एक प्रकार है [[डगलस हॉफस्टाटर]] का ब्लूपी और गोडेल, एस्चेर, बाख में फ़्लूपी। अनबाउंड लूप्स (WHILE, GOTO) को जोड़ने से भाषा सामान्य पुनरावर्ती कार्य करती है और [[ट्यूरिंग पूर्णता]] | ट्यूरिंग-पूर्ण, जैसा कि सभी वास्तविक दुनिया की कंप्यूटर प्रोग्रामिंग भाषाएं हैं।
+}}</ref> एक ऐसी भाषा है। इसकी कंप्यूटिंग शक्ति मौलिक पुनरावर्ती फलनों के साथ मेल खाती है। लूप भाषा का एक प्रकार है [[डगलस हॉफस्टाटर]] का ब्लूपी और गोडेल, एस्चेर, बाख में फ़्लूपी। अनबाउंड लूप्स (WHILE, GOTO) को जोड़ने से भाषा सामान्य पुनरावर्ती कार्य करती है और [[ट्यूरिंग पूर्णता]] | ट्यूरिंग-पूर्ण, जैसा कि सभी वास्तविक दुनिया की कंप्यूटर प्रोग्रामिंग भाषाएं हैं।
-आदिम पुनरावर्ती कार्यों की परिभाषा का तात्पर्य है कि उनकी गणना हर इनपुट पर रुक जाती है (सीमित संख्या में चरणों के बाद)। दूसरी ओर, सामान्य पुनरावर्ती कार्यों के लिए [[रुकने की समस्या]] [[अनिर्णीत समस्या]] है, भले ही वे कुल कार्य हों। यही है, ऐसे प्रोग्राम हैं जो हर इनपुट पर रुकते हैं, लेकिन जिसके लिए इसे एल्गोरिथम द्वारा सत्यापित नहीं किया जा सकता है।
+मौलिक पुनरावर्ती फलनों की परिभाषा का तात्पर्य है कि उनकी गणना हर इनपुट पर रुक जाती है (सीमित संख्या में चरणों के बाद)। दूसरी ओर, सामान्य पुनरावर्ती कार्यों के लिए [[रुकने की समस्या]] [[अनिर्णीत समस्या]] है, यदिवे कुल कार्य हों। यही है, ऐसे प्रोग्राम हैं जो हर इनपुट पर रुकते हैं, लेकिन जिसके लिए इसे एल्गोरिथम द्वारा सत्यापित नहीं किया जा सकता है।
-== Finitism और संगति परिणाम ==
+== फिनिटिज्म और संगति परिणाम ==
-आदिम पुनरावर्ती कार्य गणितीय [[finitism]] से निकटता से संबंधित हैं, और गणितीय तर्क में कई संदर्भों में उपयोग किए जाते हैं जहाँ विशेष रूप से रचनात्मक प्रणाली वांछित होती है। [[आदिम पुनरावर्ती अंकगणित]] (PRA), प्राकृतिक संख्याओं के लिए एक औपचारिक स्वयंसिद्ध प्रणाली और उन पर आदिम पुनरावर्ती कार्यों का उपयोग अक्सर इस उद्देश्य के लिए किया जाता है।
+मौलिक पुनरावर्ती फलन गणितीय [[Finitism|फ़िनिटिज़्म]] से निकटता से संबंधित हैं, और गणितीय तर्क में कई संदर्भों में उपयोग किए जाते हैं जहाँ विशेष रूप से रचनात्मक प्रणाली वांछित होती है। [[आदिम पुनरावर्ती अंकगणित]] (पीआरए), प्राकृतिक संख्याओं के लिए एक औपचारिक स्वयंसिद्ध प्रणाली और उन पर आदिम पुनरावर्ती कार्यों का उपयोग अधिकांशतः इस उद्देश्य के लिए किया जाता है।
-पीआरए पीआनो अंकगणित की तुलना में बहुत कमजोर है, जो कि परिमित प्रणाली नहीं है। फिर भी, पीआरए में संख्या सिद्धांत और प्रूफ सिद्धांत में कई परिणाम सिद्ध किए जा सकते हैं। उदाहरण के लिए, गोडेल की अपूर्णता प्रमेय को निम्नलिखित प्रमेय देते हुए PRA में औपचारिक रूप दिया जा सकता है:
+पीआरए पीआनो अंकगणित की तुलना में बहुत कमजोर है, जो कि परिमित प्रणाली नहीं है। फिर भी, पीआरए में संख्या सिद्धांत और प्रूफ सिद्धांत में कई परिणाम सिद्ध किए जा सकते हैं। उदाहरण के लिए, गोडेल की अपूर्णता प्रमेय को निम्नलिखित प्रमेय देते हुए पीआरए में औपचारिक रूप दिया जा सकता है:
-: यदि टी अंकगणित का एक सिद्धांत है जो कुछ परिकल्पनाओं को संतुष्ट करता है, गोडेल वाक्य जी के साथ<sub>''T''</sub>, तो PRA निहितार्थ Con(T)→G को सिद्ध करता है<sub>''T''</sub>.
+: यदि ''T'' गोडेल वाक्य ''G<sub>T</sub>'', के साथ कुछ परिकल्पनाओं को संतुष्ट करने वाला अंकगणित का सिद्धांत है, तो पीआरए निहितार्थ Con(''T'')→''G<sub>T</sub>''. को सिद्ध करता है।
 इसी तरह, प्रूफ थ्योरी में कई सिंटैक्टिक परिणाम PRA में सिद्ध किए जा सकते हैं, जिसका अर्थ है कि आदिम पुनरावर्ती कार्य हैं जो प्रूफ के संबंधित सिंटैक्टिक ट्रांसफॉर्मेशन को अंजाम देते हैं।
-प्रूफ थ्योरी और [[समुच्चय सिद्धान्त]] में, फ़िनिटिस्टिक कंसिस्टेंसी प्रूफ़ में दिलचस्पी है, यानी, कंसिस्टेंसी प्रूफ जो खुद फ़ाइनिस्टिक रूप से स्वीकार्य हैं। इस तरह का प्रमाण यह स्थापित करता है कि एक सिद्धांत टी की संगति का तात्पर्य एक सिद्धांत एस की संगति से है, जो एक आदिम पुनरावर्ती कार्य का निर्माण करता है, जो एस से असंगति के किसी भी प्रमाण को टी से असंगतता के प्रमाण में बदल सकता है। [[संगति प्रमाण]] के लिए एक पर्याप्त शर्त परिमित होना पीआरए में इसे औपचारिक रूप देने की क्षमता है। उदाहरण के लिए, सेट थ्योरी में कई संगति परिणाम जो कि फोर्सिंग (गणित) द्वारा प्राप्त किए जाते हैं, को सिंटैक्टिक प्रूफ के रूप में पुनर्गठित किया जा सकता है जिसे PRA में औपचारिक रूप दिया जा सकता है।
+प्रूफ सिद्धान्त और [[समुच्चय सिद्धान्त]] में, फ़िनिटिस्टिक कंसिस्टेंसी प्रूफ़ में रोचकी है, अर्थात, कंसिस्टेंसी प्रूफ जो खुद फ़ाइनिस्टिक रूप से स्वीकार्य हैं। इस तरह का प्रमाण यह स्थापित करता है कि सिद्धांत टी की संगति का तात्पर्य सिद्धांत एस की संगति से है, जो आदिम पुनरावर्ती कार्य का निर्माण करता है, जो एस से असंगति के किसी भी प्रमाण को टी से असंगतता के प्रमाण में बदल सकता है। [[संगति प्रमाण]] के लिए पर्याप्त शर्त परिमित होना पीआरए में इसे औपचारिक रूप देने की क्षमता है। उदाहरण के लिए, सेट थ्योरी में कई संगति परिणाम जो कि फोर्सिंग द्वारा प्राप्त किए जाते हैं, उन्हें सिंटैक्टिक प्रूफ के रूप में पुनर्गठित किया जा सकता है जिन्हें PRA में औपचारिक रूप दिया जा सकता है।
 == इतिहास ==
-पहले [[पुनरावर्ती परिभाषा]]ओं का गणित में अधिक या कम औपचारिक रूप से उपयोग किया गया था, लेकिन आदिम पुनरावर्तन के निर्माण का पता [[रिचर्ड डेडेकिंड]] के प्रमेय 126 में लगाया गया था, जो कि सिंड अंड सोलेन डाई ज़ाहलेन था? (1888)। यह कार्य सबसे पहले एक प्रमाण देने वाला था कि एक निश्चित पुनरावर्ती निर्माण एक अद्वितीय कार्य को परिभाषित करता है।<ref name="Smith2013">{{cite book|author=Peter Smith|title=An Introduction to Gödel's Theorems|year=2013|publisher=Cambridge University Press|isbn=978-1-107-02284-3|pages=98–99|edition=2nd}}</ref><ref name="Tourlakis2003">{{cite book|author=George Tourlakis|title=Lectures in Logic and Set Theory: Volume 1, Mathematical Logic|year=2003|publisher=Cambridge University Press|isbn=978-1-139-43942-8|page=129}}</ref><ref name="Downey2014">{{cite book|editor=Rod Downey|title=Turing's Legacy: Developments from Turing's Ideas in Logic|year=2014|publisher=Cambridge University Press|isbn=978-1-107-04348-0|page=474}}</ref>
+पहले [[पुनरावर्ती परिभाषा|पुनरावर्ती परिभाषाओं]] का गणित में अधिक या कम औपचारिक रूप से उपयोग किया गया था, लेकिन प्रारंभिक पुनरावर्तन के निर्माण का पता [[रिचर्ड डेडेकिंड]] के प्रमेय 126 में लगाया गया था, जो कि सिंड अंड सोलेन डाई ज़ाहलेन था? (1888)। यह पहला काम था जिसने प्रमाण दिया कि एक निश्चित पुनरावर्ती निर्माण एक अद्वितीय कार्य को परिभाषित करता है।<ref name="Smith2013">{{cite book|author=Peter Smith|title=An Introduction to Gödel's Theorems|year=2013|publisher=Cambridge University Press|isbn=978-1-107-02284-3|pages=98–99|edition=2nd}}</ref><ref name="Tourlakis2003">{{cite book|author=George Tourlakis|title=Lectures in Logic and Set Theory: Volume 1, Mathematical Logic|year=2003|publisher=Cambridge University Press|isbn=978-1-139-43942-8|page=129}}</ref><ref name="Downey2014">{{cite book|editor=Rod Downey|title=Turing's Legacy: Developments from Turing's Ideas in Logic|year=2014|publisher=Cambridge University Press|isbn=978-1-107-04348-0|page=474}}</ref>
-आदिम पुनरावर्ती अंकगणित सबसे पहले [[थोराल्फ़ स्कोलेम]] द्वारा प्रस्तावित किया गया था<ref>[[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.</ref> 1923 में।
-[[विल्हेम एकरमैन]] ने 1928 में साबित कर दिया था कि वर्तमान शब्दावली रोज़सा पेटर (1934) द्वारा गढ़ी गई थी, जो कि आज उनके नाम पर रखा गया कार्य आदिम पुनरावर्ती नहीं था, एक ऐसी घटना जिसने तब तक नाम बदलने की आवश्यकता को प्रेरित किया जब तक कि इसे केवल पुनरावर्ती कार्य कहा जाता था।<ref name="Tourlakis2003"/><ref name="Downey2014"/>
+प्राचीन पुनरावर्ती अंकगणित पहली बार '''1923 में [[थोराल्फ़ स्कोलेम]]''' <ref>[[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.</ref> द्वारा प्रस्तावित किया गया था।।
+[[विल्हेम एकरमैन|'''विल्हेम एकरमैन''']] द्वारा 1928 में यह प्रमाण करने के बाद कि वर्तमान शब्दावली को रोज़ा पेटर (1934) द्वारा गढ़ा गया था कि आज जिस फलन का नाम उनके नाम पर रखा गया है, वह आदिम पुनरावर्ती नहीं था, एक ऐसी घटना जिसने उस समय तक नाम बदलने की आवश्यकता को प्रेरित किया जिसे केवल पुनरावर्ती कार्य कहा जाता था।<ref name="Tourlakis2003" /><ref name="Downey2014" />
 == यह भी देखें ==
 * ग्रेज़गोर्स्की पदानुक्रम
 * [[रिकर्सन (कंप्यूटर विज्ञान)]]
-* [[आदिम पुनरावर्ती कार्यात्मक]]
+* [[आदिम पुनरावर्ती कार्यात्मक|मौलिक पुनरावर्ती फलनात्मक]]
 * [[डबल रिकर्सन]]
-* [[आदिम पुनरावर्ती सेट समारोह]]
+* [[आदिम पुनरावर्ती सेट समारोह|प्राचीन पुनरावर्ती सेट फलन]]
-* [[आदिम पुनरावर्ती क्रमिक कार्य]]
+* [[आदिम पुनरावर्ती क्रमिक कार्य|प्राचीन पुनरावर्ती क्रमिक कार्य]]
 ==टिप्पणियाँ==
@@ Line 373: / Line 366: @@
 * Brainerd, W.S., Landweber, L.H. (1974), ''Theory of Computation'', Wiley, {{isbn|0-471-09585-0}}
 * {{cite journal | last1=Fischer | first1=Michael J. | last2=Fischer | first2=Robert P. | last3=Beigel | first3=Richard | title=Primitive Recursion without Implicit Predecessor | journal=[[ACM SIGACT|ACM SIGACT News]] | date=November 1989 | volume=20| issue=4| pages=87–91 | url=https://doi.org/10.1145/74074.74089 | doi=10.1145/74074.74089| s2cid=33850327 }}
-* [[Robert I. Soare]], ''Recursively Enumerable Sets and Degrees'', Springer-Verlag, 1987.  {{isbn|0-387-15299-7}}
+* [[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 P. Burgess|John Burgess]], [[Richard Jeffrey]] (2002), ''Computability and Logic: Fourth Edition'', Cambridge University Press, Cambridge, UK. Cf pp.&nbsp;70–71.
@@ Line 379: / Line 372: @@
 * Daniel Severin 2008, ''Unary primitive recursive functions'', J. Symbolic Logic Volume 73, Issue 4, pp.&nbsp;1122–1138 [https://arxiv.org/abs/cs/0603063v3 arXiv] [https://projecteuclid.org/euclid.jsl/1230396909 projecteuclid] {{doi|10.2178/jsl/1230396909}} {{JSTOR|275903221}}
-{{Mathematical logic}}
+[[Category:CS1 errors]]
-[[Category: संगणनीयता सिद्धांत]] [[Category: संगणना का सिद्धांत]] [[Category: कार्य और मानचित्रण]] [[Category: प्रत्यावर्तन]]
+[[Category:CS1 maint]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 03/02/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:कार्य और मानचित्रण]]
+[[Category:प्रत्यावर्तन]]
+[[Category:संगणना का सिद्धांत]]
+[[Category:संगणनीयता सिद्धांत]]

Anonymous

Search