मौलिक पुनरावर्ती फलन

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

मौलिक पुनरावर्ती फलनों का महत्व इस तथ्य में निहित है कि संख्या सिद्धांत (और सामान्यतः गणित में) में अध्ययन किए जाने वाले अधिकांश संगणनीय कार्य प्राचीन पुनरावर्ती हैं। उदाहरण के लिए, योग और विभाजन (गणित), क्रमगुणित और चरघातांकी फलन, और जो फलन 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]

Anonymous

Search