आदिम पुनरावर्ती कार्य

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

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

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

परिभाषा

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

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

1. Constant functions C^k
   _n: For each natural number n and every k, the k-ary constant function, defined by $C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n$, is primitive recursive.
2. Successor function: The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), that is, $S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1$, is primitive recursive.
3. Projection function $P_{i}^{k}$: For all natural numbers $i,k$ such that $1\leq i\leq k$, the k-ary function defined by $P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}$ is primitive recursive.

इन स्वयंसिद्धों द्वारा दिए गए ऑपरेशन (गणित) को लागू करके अधिक जटिल आदिम पुनरावर्ती कार्य प्राप्त किए जा सकते हैं:

4. Composition operator $\circ \,$ (also called the substitution operator): Given an m-ary function $h(x_{1},\ldots ,x_{m})\,$ and m k-ary functions $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})$:
   $$h\circ (g_{1},\ldots ,g_{m})\ {\stackrel {\mathrm {def} }{=}}\ f,\quad {\text{where}}\quad f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})).$$
5. Primitive recursion operator ρ: Given the k-ary function $g(x_{1},\ldots ,x_{k})\,$ and the (k + 2)-ary function $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}}$$

   Interpretation:

   The function f acts as a for-loop from 0 up to the value of its first argument. The rest of the arguments for f, denoted here with x₁, ..., x_k, are a set of initial conditions for the for-loop which may be used by it during calculations but which are immutable by it. The functions g and h on the right-hand side of the equations that define f represent the body of the loop, which performs calculations. The function g is used only once to perform initial calculations. Calculations for subsequent steps of the loop are performed by h. The first parameter of h is fed the "current" value of the for-loop's index. The second parameter of h is fed the result of the for-loop's previous calculations, from previous steps. The rest of the parameters for h are those immutable initial conditions for the for-loop mentioned earlier. They may be used by h to perform calculations but they will not themselves be altered by h.

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

उदाहरण

• $C_{0}^{1}$ is a 1-ary function which returns $0$ for every input: $C_{0}^{1}(x)=0$.
• $C_{1}^{1}$ is a 1-ary function which returns $1$ for every input: $C_{1}^{1}(x)=1$.
• $C_{3}^{0}$ is a 0-ary function, i.e. a constant: $C_{3}^{0}=3$.
• $P_{1}^{1}$ is the identity function on the natural numbers: $P_{1}^{1}(x)=x$.
• $P_{1}^{2}$ and $P_{2}^{2}$ is the left and right projection on natural number pairs, respectively: $P_{1}^{2}(x,y)=x$ and $P_{2}^{2}(x,y)=y$.
• $S\circ S$ is a 1-ary function that adds 2 to its input, $(S\circ S)(x)=x+2$.
• $S\circ C_{0}^{1}$ is a 1-ary function which returns 1 for every input: $(S\circ C_{0}^{1})(x)=S(C_{0}^{1}(x))=S(0)=1$. That is, $S\circ C_{0}^{1}$ and $C_{1}^{1}$ are the same function: $S\circ C_{0}^{1}=C_{1}^{1}$. In a similar way, every $C_{n}^{1}$ can be expressed as a composition of appropriately many $S$ and $C_{0}^{1}$.

जोड़

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

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

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

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

दोहरीकरण

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

गुणन

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

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

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

पूर्ववर्ती

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

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

कटा हुआ घटाव

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

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

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

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

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

कुछ सेटिंग्स में आदिम पुनरावर्ती कार्यों पर विचार करना स्वाभाविक है जो इनपुट टुपल्स के रूप में लेते हैं जो सत्य मानों के साथ संख्याओं को मिलाते हैं (जो कि सत्य के लिए t है और गलत के लिए f है), या जो आउटपुट के रूप में सत्य मान उत्पन्न करते हैं। इसे किसी निश्चित तरीके से संख्याओं के साथ सत्य मानों की पहचान करके पूरा किया जा सकता है। उदाहरण के लिए, संख्या 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) जोड़ते हैं।

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

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

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

# जोड़: ए + बी

1. गुणन: a×b

# घातांक: ए^{ख</सुप>}

# फैक्टोरियल ए! : 0! = 1, ए'! = ए! × ए'

# पूर्व (ए): (पूर्ववर्ती या कमी): यदि ए> 0 तो ए -1 और 0

1. उचित घटाव a ∸ b: यदि a ≥ b तो a-b और 0

# न्यूनतम (ए₁, ... ए_n)

# अधिकतम (ए₁, ... ए_n)

1. पूर्ण अंतर: | ए-बी | =_def (ए ∸ बी) + (बी ∸ ए)
2. ~sg(a): NOT[signum(a)]: अगर a=0 तो 1 और 0

# एसजी (ए): साइनम (ए): यदि ए = 0 तो 0 और 1

1. ए | b: (a b को विभाजित करता है): यदि b=k×a कुछ k के लिए तो 0 और 1
2. Remainder(a, b): बचे हुए अगर b समान रूप से विभाजित नहीं करता है। एमओडी (ए, बी) भी कहा जाता है
3. ए = बी: एसजी | ए - बी | (क्लीन की प्रथा को 0 से सत्य और 1 से असत्य का प्रतिनिधित्व करना था; वर्तमान में, विशेष रूप से कंप्यूटरों में, सबसे आम सम्मेलन रिवर्स है, अर्थात् 1 से सत्य और 0 से गलत का प्रतिनिधित्व करने के लिए, जो यहाँ और ~sg में sg को बदलने की मात्रा है। अगला आइटम)
4. a < b: sg( a' ∸ b )
5. Pr(a): a एक अभाज्य संख्या है Pr(a) =_def a>1 और नहीं (मौजूद c)_1<c<a [सी|ए]
6. पी_i: i+1-st अभाज्य संख्या
7. (ए)_i: पी के प्रतिपादक_i a में: अद्वितीय x ऐसा है कि p_i^x|a और NOT(p_i^{एक्स'}|ए)

# एलएच (ए): लंबाई या गायब न होने वाले घातांक की संख्या

# लो (ए, बी): (आधार बी के लघुगणक): यदि ए, बी> 1 तो सबसे बड़ा एक्स ऐसा है कि बी^{एक्स </सुप> | एक अन्य 0}

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

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

• NOT_Q('x') .

* क्यू या आर: क्यू ('एक्स') वी आर ('एक्स'),

* क्यू और आर: क्यू ('एक्स') और आर ('एक्स'),

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

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

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

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

φ(x) =

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

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

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

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

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

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

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

$h(0)=C$

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

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

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

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

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

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

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

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

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

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

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

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

सीमाएं

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

The primitive recursive functions of one argument (i.e., unary functions) can be 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 n-th definition of a primitive recursive function in this enumeration can be effectively determined from n. Indeed if one uses some Gödel numbering to encode definitions as numbers, then this n-th definition in the list is computed by a primitive recursive function of n. Let f_n denote the unary primitive recursive function given by this definition.

Now define the "evaluator function" ev with two arguments, by ev(i,j) = f_i(j). Clearly ev is total and computable, since one can effectively determine the definition of f_i, and being a primitive recursive function f_i is itself total and computable, so f_i(j) is always defined and effectively computable. However a diagonal argument will show that the function ev of two arguments is not primitive recursive.

Suppose ev were primitive recursive, then the unary function g defined by g(i) = S(ev(i,i)) would also be primitive recursive, as it is defined by composition from the successor function and ev. But then g occurs in the enumeration, so there is some number n such that g = f_n. But now g(n) = S(ev(n,n)) = S(f_n(n)) = S(g(n)) gives a contradiction.

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

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

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

वेरिएंट

लगातार कार्य

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

कमजोर आदिम पुनरावर्तन

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

${\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}}$ पुनरावृत्त कार्यों के वर्ग को उसी तरह परिभाषित किया जाता है जैसे इस कमजोर नियम को छोड़कर आदिम पुनरावर्ती कार्यों के वर्ग को। इन्हें आदिम पुनरावर्ती कार्यों का उचित उपसमुच्चय माना जाता है।

अतिरिक्त आदिम पुनरावर्ती रूप

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

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

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

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

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

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

Finitism और संगति परिणाम

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

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

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

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

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

इतिहास

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

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

यह भी देखें

• ग्रेज़गोर्स्की पदानुक्रम

डबल रिकर्सन (कंप्यूटर विज्ञान)

• आदिम पुनरावर्ती कार्यात्मक
• दोहरा पुनरावर्तन
• आदिम पुनरावर्ती सेट समारोह
• आदिम पुनरावर्ती क्रमिक कार्य

संदर्भ

• 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