जनरल रिकर्सिव फंक्शन: Difference between revisions

Revision as of 11:22, 9 August 2023

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

फ़ंक्शंस के अन्य समकक्ष स्क्वायर लैम्ब्डा कैलकुलस के फ़ंक्शंस हैं, जिनकी गणना मार्कोव एल्गोरिथ्म द्वारा की जा सकती है।

मानों के साथ सभी टोटल रिकर्सिव फ़ंक्शन का उपसमूह ${0,1}$ को कम्प्यूटेशनल काॅम्पलेक्सिटी थ्योरी में r (काॅम्पलेक्सिटी) के रूप में जाना जाता है।

परिभाषा

μ-रिकर्सिव फ़ंक्शन (या सामान्य रिकर्सिव फ़ंक्शन) पार्शियल फंक्शन हैं, जो प्राकृतिक संख्याओं के सीमित टपल्स लेते हैं और एकल प्राकृतिक संख्या लौटाते हैं। वे पार्शियल फंक्शन का सबसे छोटा वर्ग हैं, जिसमें प्रारंभिक फ़ंक्शंस सम्मिलित होते हैं और संरचना, स्यूडो रिकर्सन और μ ऑपरेटर या मिनिमाइजेशन ऑपरेटर $μ$ के अनुसार विवृत है।

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

स्यूडो या जनरल फंक्शन:

काॅन्ट्यूनिटी फंक्शन $C k n$ : प्रत्येक प्राकृतिक संख्या के लिए $n$ और हर का मान $k$ हैं।
$C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n$

वैकल्पिक परिभाषाएँ शून्य फ़ंक्शन का उपयोग स्यूडो फ़ंक्शन के रूप में करती हैं, जो सदैव शून्य लौटाता है, और शून्य फ़ंक्शन, सक्सेसर फंक्शन और कंपोज़िशन ऑपरेटर से काॅन्ट्यूनिटी फंक्शन का निर्माण करता है।
सक्सेसर फंक्शन S:
$S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1\,$
प्रोजेक्शन फंक्शन $P_{i}^{k}$ (आइडेंटिकल फ़ंक्शन भी कहा जाता है): सभी प्राकृतिक संख्याओं के लिए $i,k$ ऐसा है कि $1\leq i\leq k$ :
$P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}\,.$

ऑपरेटर्स (ऑपरेटर द्वारा परिभाषित फ़ंक्शन का डोमेन तर्कों के मानों का सेट है, जैसे कि गणना के दौरान किया जाने वाला प्रत्येक फ़ंक्शन एप्लिकेशन को अच्छी तरह से परिभाषित करने के बाद उपयुक्त परिणाम प्रदान करता है):

कंपोजीशन आपरेटर $\circ \,$ (प्रतिस्थापन ऑपरेटर भी कहा जाता है): एम-एरे फ़ंक्शन दिया गया है, इसके आधार पर $h(x_{1},\ldots ,x_{m})\,$ और एम के-ऐरे फंक्शन $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})).$

इसका अर्थ है कि $f(x_{1},\ldots ,x_{k})$ केवल तभी परिभाषित किया गया है, इसके आधार पर $g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}),$ और $h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))$ सभी परिभाषित हैं।
स्यूडो रिकर्सन ऑपरेटर $ρ$ : 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 -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(y,x_{1},\ldots ,x_{k})$ केवल तभी परिभाषित किया गया है, $g(x_{1},\ldots ,x_{k})$ और $h(z,f(z,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$ सभी के लिए $z<y.$ के अनुसार परिभाषित किया गया हैं।
मिनिमाइजेशन ऑपरेटर $μ$ : (k+1)-ऐरे फंक्शन दिया गया है $f(y,x_{1},\ldots ,x_{k})\,$ , के-ऐरे फंक्शन $\mu (f)$ द्वारा परिभाषित किया गया है:
${\begin{aligned}\mu (f)(x_{1},\ldots ,x_{k})=z{\stackrel {\mathrm {def} }{\iff }}\ f(i,x_{1},\ldots ,x_{k})&>0\quad {\text{for}}\quad i=0,\ldots ,z-1\quad {\text{and}}\\f(z,x_{1},\ldots ,x_{k})&=0\quad \end{aligned}}$

सहजता से, मिनिमाइजेशन खोजता है- इसके आधार पर 0 से खोज प्रारंभ करना और ऊपर की ओर बढ़ता हैं- इसका सबसे छोटा तर्क जो फ़ंक्शन को शून्य पर लौटने का कारण बनता है, यदि ऐसा कोई तर्क नहीं है, या यदि कोई किसी तर्क का सामना करता है जिसके लिए $f$ परिभाषित नहीं है, तो खोज कभी समाप्त नहीं होती, और $\mu (f)$ तर्क के लिए $(x_{1},\ldots ,x_{k}).$ द्वारा परिभाषित नहीं करता है।

जबकि कुछ लाइब्रेरी में μ-ऑपरेटर का उपयोग किया जाता हैं, जैसा कि यहां परिभाषित किया गया है,^[5]^[6] यह मान इसके अतिरिक्त उपयोग किया जा सकता है।^[7]^[8] यहाँ पर μ-ऑपरेटर को टोटल फंक्शन पर $f$ के द्वारा लागू किया जाता हैं। यद्यपि यह यहां दी गई परिभाषा की तुलना में μ-ऑपरेटर को प्रतिबंधित करता है, इसका μ-रिकर्सिव फ़ंक्शन का वर्ग समान रहता है, जो क्लेन के सामान्य फॉर्म प्रमेय (सामान्य फॉर्म प्रमेय देखें) जिससे इसका अनुसरण करते हैं।^[5]^[6] इस प्रकार इसका एकमात्र अंतर यह है कि यह अनिर्णीत को प्रदान करता है कि क्या विशिष्ट फ़ंक्शन परिभाषा μ-रिकर्सिव फ़ंक्शन को परिभाषित करती है, क्योंकि यह अनिर्णीत है कि क्या गणना योग्य (अर्ताथ μ-रिकर्सिव) फ़ंक्शन कुल है।^[7]

स्ट्रांग इक्ववैलिटी ऑपरेटर $\simeq$ पार्शियल μ-रिकर्सिव फ़ंक्शन की तुलना करने के लिए उपयोग किया जा सकता है। इसे सभी आंशिक फलनों f और g के लिए परिभाषित किया गया है।

f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})

यदि और केवल तभी मान्य है, जब तर्कों के किसी भी विकल्प के लिए या तो दोनों फ़ंक्शन परिभाषित हैं और उनके मान समान हैं या दोनों फ़ंक्शन अपरिभाषित हैं।

उदाहरण

मिनिमाइज़ेशन ऑपरेटर को सम्मिलित न करने वाले उदाहरण स्यूडो रिकर्सिव फ़ंक्शन उदाहरण पर पाए जा सकते हैं।

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

पूर्णांक वर्गमूल का $x$ न्यूनतम $z$ के रूप में परिभाषित किया जा सकता है, इस प्रकार यह मान इस प्रकार है कि $(z+1)^{2}>x$ न्यूनतमकरण ऑपरेटर का उपयोग करते हुए, एक सामान्य पुनरावर्ती परिभाषा है $\operatorname {Isqrt} =\mu (\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))$ , जहाँ $Not$ , $Gt$ , and $Mul$ लाॅजिकल निगेशन, इससे बड़ा, और गुणा,^[9] वास्तविकता में, $(\operatorname {Not} \circ \operatorname {Gt} \circ (\operatorname {Mul} \circ (S\circ P_{1}^{2},S\circ P_{1}^{2}),P_{2}^{2}))\;(z,x)=(\lnot S(z)*S(z)>x)$ is 0 यदि $S(z)*S(z)>x$ उपयोग करता हैं। जहाँ पर $\operatorname {Isqrt} (x)$ is the least $z$ जिसके लिए $S(z)*S(z)>x$ उपयोग करता हैँ। निषेध जंक्टर $Not$ से आवश्यकता है $Gt$ सत्य को एन्कोड करता है, 1, जबकि $μ$ 0 ढूंढता है।

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

टोटल रिकर्सिव फ़ंक्शन

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

संगणना के अन्य मॉडलों के साथ समतुल्यता

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

अनबाउंड सर्च ऑपरेटर स्यूडो रिकर्सन के नियमों द्वारा परिभाषित नहीं है क्योंकि वे इनफाइनाइट लूप (अपरिभाषित मान) के लिए सिस्टम प्रदान नहीं करते हैं।

सामान्य रूपी प्रमेय

क्लेन का t विधेय क्लीन के कारण सामान्य रूप प्रमेय कहता है कि प्रत्येक k के लिए स्यूडो रिकर्सिव फ़ंक्शन $U(y)\!$ और $T(y,e,x_{1},\ldots ,x_{k})\!$ हैं। यह इस प्रकार हैं कि किसी भी μ-रिकर्सिव फ़ंक्शन के लिए $f(x_{1},\ldots ,x_{k})\!$ k मुक्त चर के साथ e ऐसा है-

f(x_{1},\ldots ,x_{k})\simeq U(\mu (T)(e,x_{1},\ldots ,x_{k}))

फ़ंक्शन f के लिए संख्या e को इंडेक्स या गोडेल नंबर कहा जाता है।^[10]^: 52–53 इस परिणाम का परिणाम यह है कि किसी भी μ-रिकर्सिव फ़ंक्शन को (कुल) स्यूडो रिकर्सिव फ़ंक्शन पर लागू μ ऑपरेटर के एकल उदाहरण का उपयोग करके परिभाषित किया जा सकता है।

मार्विन मिंस्की इसका निरीक्षण करते हैं $U$ ऊपर परिभाषित संक्षेप में सार्वभौमिक ट्यूरिंग मशीन के μ-रिकर्सिव समकक्ष है:

यू का निर्माण करने के लिए एक सामान्य-पुनरावर्ती फ़ंक्शन यू (एन, एक्स) की परिभाषा लिखना है जो संख्या एन की सही व्याख्या करता है और एक्स के उचित फ़ंक्शन की गणना करता है। यू को सीधे बनाने में अनिवार्य रूप से उतना ही प्रयास, और मूल रूप से वही विचार शामिल होंगे, जितना हमने यूनिवर्सल ट्यूरिंग मशीन के निर्माण में निवेश किया है। ^[11]

प्रतीकवाद

साहित्य में अनेक प्रकार के प्रतीकों का प्रयोग किया जाता है। प्रतीकवाद का उपयोग करने का फायदा यह है कि ऑपरेटरों को के अंदर करके फ़ंक्शन की व्युत्पत्ति की जाती है, जिसे कॉम्पैक्ट रूप में लिखना सरल होता है। निम्नलिखित में पैरामीटर्स की स्ट्रिंग x₁, ..., x_n इसे x के रूप में संक्षिप्त किया गया है:

काॅन्ट्यूनिटी फंक्शन: क्लेन cⁿ
_q(x) = q का उपयोग करता है, और बूलोस-बर्गेस-जेफरी (2002) (b-b-j) संक्षिप्त नाम const_n( x) = n का उपयोग करते हैं:

उदाहरण के लिए c⁷
₁₃ (r, s, t, u, v, w, x) = 13

उदा. const₁₃ (r, s, t, u, v, w, x) = 13

सक्सेसर फंक्शन: क्लेन सक्सेसर के लिए x' और S का उपयोग करता है। चूंकि सक्सेसर को स्यूडो माना जाता है, अधिकांश ग्रंथ एपॉस्ट्रॉफ़ी का उपयोग इस प्रकार करते हैं:

s(a) = a +1 =_def a', जहां 1 =_def 0', 2 =_def 0 , आदि।

आइडेंटिटी फंक्शन: क्लेन (1952) uⁿ
_i का उपयोग करता है वेरिएबल x_i पर आइडेंटिटी फंक्शन को इंगित करने के लिए, b-b-jⁿ
_i चर x₁ पर x_n को आइडेंटिटी फंक्शन id का उपयोग करें:

uⁿ
_i( x ) = idⁿ
_i( x ) = x_i : जैसे u⁷
₃ = id⁷
₃ (r, s, t, u, v, w, x) = t

रचना (प्रतिस्थापन) ऑपरेटर: क्लेन बोल्ड-फेस 's'^m
_n का उपयोग करता है, उसके सक्सेसर के साथ भ्रमित न हों!। इस प्रकार सुपरस्क्रिप्ट m, m^f_m को संदर्भित करता है, जबकि इस प्रकार सबस्क्रिप्ट n, n वेरिएबल x_n को संदर्भित करता है :

यदि हमें h(x)=g(f) दिया गया है₁(x), ..., f_m(x) )

h(x) = sⁿ
_m(g, f₁, ... , f_m )

इसी प्रकार, उप- और सुपरस्क्रिप्ट के बिना, b-b-j लिखते हैं:

h(x')= Cn[g, f₁ ,..., f_m](x)

स्यूडो पुनरावर्तन: क्लेन प्रतीक rⁿ का उपयोग करता है(बेस स्टेप, इंडक्शन स्टेप) जहां n वेरिएबल्स की संख्या को इंगित करता है, इस प्रकार b-b-j Pr(बेस स्टेप, इंडक्शन स्टेप)(x) का उपयोग करते हैं। जो इस प्रकार दिया गया हैं:

आधार चरण: h( 0, x )= f( x ), और
प्रेरण चरण: h( y+1, x ) = g( y, h(y, x),x )

उदाहरण: a + b का स्यूडो रिकर्सन परिभाषा:

आधार चरण: f( 0, a ) = a = U¹
₁(a)
प्रेरण चरण: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U³
₂(b, c, a))

r²{ u¹
₁(a), S [ (U³
₂( b, c, a ) ] }

{u¹
₁(a), s[(u³
₂(b, c, a) ] }

उदाहरण: क्लेन उदाहरण देता है कि f(b, a) = b + a की रिकर्सिव व्युत्पत्ति वेरिएबल a और b की व्युत्क्रम नोटिस को कैसे करें। वह 3 प्रारंभिक कार्यों से प्रारंभ करता है

s(a) = a'
u¹
₁(a) = a
u³
₂(b, c, a) = c
g(b, c, a) = s(u³
₂(b, c, a)) = c'
आधार चरण: h( 0, a ) = U¹
₁(a)

प्रेरण चरण: h(b', a) = g(b, h(b, a), a)

वह यहां पहुंचता है:

a+b = r²[u¹
₁, s³
₁(s, u³
₂) ]

उदाहरण

यह भी देखें

संदर्भ

↑ "Recursive Functions". द स्टैनफोर्ड इनसाइक्लोपीडिया ऑफ फिलॉसफी. Metaphysics Research Lab, Stanford University. 2021.
↑ Stanford Encyclopedia of Philosophy, Entry Recursive Functions, Sect.1.7: "[The class of μ-recursive functions] turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church."
↑ Kleene, Stephen C. (1936). "λ-definability and recursiveness". Duke Mathematical Journal. 2 (2): 340–352. doi:10.1215/s0012-7094-36-00227-2.
↑ Turing, Alan Mathison (Dec 1937). "Computability and λ-Definability". Journal of Symbolic Logic. 2 (4): 153–163. doi:10.2307/2268280. JSTOR 2268280. S2CID 2317046. Proof outline on p.153: $\lambda {\mbox{-definable}}$ ${\stackrel {triv}{\implies }}$ $\lambda {\mbox{-}}K{\mbox{-definable}}$ ${\stackrel {160}{\implies }}$ ${\mbox{Turing computable}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ ^[3] $\lambda {\mbox{-definable}}$
↑ ^5.0 ^5.1 Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972
↑ ^6.0 ^6.1 Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007
↑ ^7.0 ^7.1 Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997
↑ Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982
↑ defined in Primitive recursive function#Junctors, Primitive recursive function#Equality predicate, and Primitive recursive function#Multiplication
↑ Stephen Cole Kleene (Jan 1943). "पुनरावर्ती विधेय और परिमाणक" (PDF). Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.1090/S0002-9947-1943-0007371-8.
↑ Minsky 1972, pp. 189.

Kleene, Stephen (1991) [1952]. Introduction to Metamathematics. Walters-Noordhoff & North-Holland. ISBN 0-7204-2103-9.
Soare, R. (1999) [1987]. Recursively enumerable sets and degrees: A Study of Computable Functions and Computably Generated Sets. Springer-Verlag. ISBN 9783540152996.
Minsky, Marvin L. (1972) [1967]. Computation: Finite and Infinite Machines. Prentice-Hall. pp. 210–5. ISBN 9780131654495.

On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

Boolos, George; Burgess, John; Jeffrey, Richard (2002). "6.2 Minimization". Computability and Logic (4th ed.). Cambridge University Press. pp. 70–71. ISBN 9780521007580.

बाहरी संबंध

[1] "Recursive Functions". द स्टैनफोर्ड इनसाइक्लोपीडिया ऑफ फिलॉसफी. Metaphysics Research Lab, Stanford University. 2021.

[2] Stanford Encyclopedia of Philosophy, Entry Recursive Functions, Sect.1.7: "[The class of μ-recursive functions] turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church."

[3] Kleene, Stephen C. (1936). "λ-definability and recursiveness". Duke Mathematical Journal. 2 (2): 340–352. doi:10.1215/s0012-7094-36-00227-2.

[4] Turing, Alan Mathison (Dec 1937). "Computability and λ-Definability". Journal of Symbolic Logic. 2 (4): 153–163. doi:10.2307/2268280. JSTOR 2268280. S2CID 2317046. Proof outline on p.153: $\lambda {\mbox{-definable}}$ ${\stackrel {triv}{\implies }}$ $\lambda {\mbox{-}}K{\mbox{-definable}}$ ${\stackrel {160}{\implies }}$ ${\mbox{Turing computable}}$ ${\stackrel {161}{\implies }}$ $\mu {\mbox{-recursive}}$ ${\stackrel {Kleene}{\implies }}$ ^[3] $\lambda {\mbox{-definable}}$

[Enderton.1972-5] 5.0 ^5.1 Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972

[Boolos.Burgess.Jeffrey.2007-6] 6.0 ^6.1 Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007

[Jones.1997-7] 7.0 ^7.1 Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997

[8] Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982

[9] Primitive recursive function#Junctors, Primitive recursive function#Equality predicate, and Primitive recursive function#Multiplication

[10] Stephen Cole Kleene (Jan 1943). "पुनरावर्ती विधेय और परिमाणक" (PDF). Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.1090/S0002-9947-1943-0007371-8.

[FOOTNOTEMinsky1972189-11] Minsky 1972, pp. 189.

[1]

[2]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[3]

@@ Line 1: / Line 1: @@
 {{Short description|One of several equivalent definitions of a computable function}}
-[[गणितीय तर्क]] और [[कंप्यूटर विज्ञान]] में, सामान्य पुनरावर्ती फ़ंक्शन, आंशिक पुनरावर्ती फ़ंक्शन, या μ-पुनरावर्ती फ़ंक्शन [[प्राकृतिक संख्या]]ओं से प्राकृतिक संख्याओं तक आंशिक फ़ंक्शन है जो सहज ज्ञान युक्त अर्थ में गणना योग्य है - साथ ही गणना योग्य फ़ंक्शन में भी। यदि फ़ंक्शन कुल है, तो इसे कुल पुनरावर्ती फ़ंक्शन भी कहा जाता है (कभी-कभी पुनरावर्ती फ़ंक्शन के लिए छोटा किया जाता है)।<ref>{{Cite book|chapter-url=https://plato.stanford.edu/entries/recursive-functions/#PartRecuFuncPartRecuFuncREC|title = द स्टैनफोर्ड इनसाइक्लोपीडिया ऑफ फिलॉसफी|chapter = Recursive Functions|year = 2021|publisher = Metaphysics Research Lab, Stanford University}}</ref> कम्प्यूटेबिलिटी सिद्धांत (गणना) में, यह दिखाया गया है कि μ-पुनरावर्ती फ़ंक्शन सटीक रूप से वे फ़ंक्शन हैं जिनकी गणना [[ट्यूरिंग मशीन]]ों द्वारा की जा सकती है<ref>[[Stanford Encyclopedia of Philosophy]], Entry [http://plato.stanford.edu/entries/recursive-functions Recursive Functions], Sect.1.7: "[The class of μ-recursive functions] ''turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church.''"</ref>{{#tag:ref|{{cite journal | jstor=2268280 |first=Alan Mathison |last=Turing | author-link=Alan Turing | title=Computability and λ-Definability | journal=[[Journal of Symbolic Logic]] | volume=2 | number=4 | pages=153–163 | date=Dec 1937 |doi=10.2307/2268280 |s2cid=2317046 }} Proof outline on p.153: <math>\lambda\mbox{-definable}</math> <math>\stackrel{triv}{\implies}</math> <math>\lambda\mbox{-}K\mbox{-definable}</math> <math>\stackrel{160}{\implies}</math> <math>\mbox{Turing computable}</math> <math>\stackrel{161}{\implies}</math> <math>\mu\mbox{-recursive}</math> <math>\stackrel{Kleene}{\implies}</math><ref>{{cite journal | url=https://projecteuclid.org/euclid.dmj/1077489488 |first=Stephen C. |last=Kleene | author-link=Stephen C. Kleene | title=λ-definability and recursiveness | journal=[[Duke Mathematical Journal]] | volume=2 | number=2 | pages=340–352 |year=1936 | doi=10.1215/s0012-7094-36-00227-2}}</ref> <math>\lambda\mbox{-definable}</math>}} (यह उन प्रमेयों में से है जो चर्च-ट्यूरिंग थीसिस का समर्थन करता है)। μ-पुनरावर्ती फ़ंक्शन [[आदिम पुनरावर्ती कार्य]]ों से निकटता से संबंधित हैं, और उनकी आगमनात्मक परिभाषा (नीचे) आदिम पुनरावर्ती कार्यों पर आधारित है। हालाँकि, प्रत्येक कुल पुनरावर्ती फ़ंक्शन आदिम पुनरावर्ती फ़ंक्शन नहीं है - सबसे प्रसिद्ध उदाहरण [[एकरमैन फ़ंक्शन]] है।
+[[गणितीय तर्क]] और [[कंप्यूटर विज्ञान]] में, '''जनरल रिकर्सिव फंक्शन''', पार्शियल रिकर्सिव फंक्शन, या μ-रिकर्सिव फ़ंक्शन [[प्राकृतिक संख्या|प्राकृतिक संख्याओं]] से प्राकृतिक संख्याओं तक पार्शियल फ़ंक्शन है, जो सहज ज्ञान युक्त अर्थ में गणना योग्य है - इसके साथ ही गणना योग्य फ़ंक्शन में भी इसका उपयोग करता हैं। यदि फ़ंक्शन कुल फंक्शन को प्रदर्शित करता है, तो इसे टोटल रिकर्सिव फ़ंक्शन भी कहा जाता है, इसका आधार पर कभी-कभी रिकर्सिव फ़ंक्शन के लिए इसे छोटा कर दिया जाता है।<ref>{{Cite book|chapter-url=https://plato.stanford.edu/entries/recursive-functions/#PartRecuFuncPartRecuFuncREC|title = द स्टैनफोर्ड इनसाइक्लोपीडिया ऑफ फिलॉसफी|chapter = Recursive Functions|year = 2021|publisher = Metaphysics Research Lab, Stanford University}}</ref> इस प्रकार कम्प्यूटेबिलिटी सिद्धांत (गणना) में, यह दिखाया गया है कि μ-रिकर्सिव फ़ंक्शन सटीक रूप से ऐसे फ़ंक्शन हैं, जिनकी गणना [[ट्यूरिंग मशीन]] द्वारा की जा सकती है,<ref>[[Stanford Encyclopedia of Philosophy]], Entry [http://plato.stanford.edu/entries/recursive-functions Recursive Functions], Sect.1.7: "[The class of μ-recursive functions] ''turns out to coincide with the class of the Turing-computable functions introduced by Alan Turing as well as with the class of the λ-definable functions introduced by Alonzo Church.''"</ref>{{#tag:ref|{{cite journal | jstor=2268280 |first=Alan Mathison |last=Turing | author-link=Alan Turing | title=Computability and λ-Definability | journal=[[Journal of Symbolic Logic]] | volume=2 | number=4 | pages=153–163 | date=Dec 1937 |doi=10.2307/2268280 |s2cid=2317046 }} Proof outline on p.153: <math>\lambda\mbox{-definable}</math> <math>\stackrel{triv}{\implies}</math> <math>\lambda\mbox{-}K\mbox{-definable}</math> <math>\stackrel{160}{\implies}</math> <math>\mbox{Turing computable}</math> <math>\stackrel{161}{\implies}</math> <math>\mu\mbox{-recursive}</math> <math>\stackrel{Kleene}{\implies}</math><ref>{{cite journal | url=https://projecteuclid.org/euclid.dmj/1077489488 |first=Stephen C. |last=Kleene | author-link=Stephen C. Kleene | title=λ-definability and recursiveness | journal=[[Duke Mathematical Journal]] | volume=2 | number=2 | pages=340–352 |year=1936 | doi=10.1215/s0012-7094-36-00227-2}}</ref> <math>\lambda\mbox{-definable}</math>}} यह उन प्रमेयों में से प्रमुख है, जो चर्च-ट्यूरिंग थीसिस का समर्थन करता है। इसके आधार पर μ-रिकर्सिव फ़ंक्शन [[आदिम पुनरावर्ती कार्य|रिकर्सिव फ़ंक्शन]] की निकटता से संबंधित हैं, और उनकी आगमनात्मक परिभाषा (नीचे) स्यूडो रिकर्सिव फ़ंक्शन पर आधारित है। चूंकि, प्रत्येक टोटल रिकर्सिव फ़ंक्शन स्यूडो रिकर्सिव फ़ंक्शन नहीं है - इसका सबसे प्रसिद्ध उदाहरण [[एकरमैन फ़ंक्शन]] है।
-फ़ंक्शंस के अन्य समकक्ष वर्ग [[लैम्ब्डा कैलकुलस]] के फ़ंक्शंस और फ़ंक्शंस हैं जिनकी गणना [[मार्कोव एल्गोरिथ्म]] द्वारा की जा सकती है।
+फ़ंक्शंस के अन्य समकक्ष स्क्वायर [[लैम्ब्डा कैलकुलस]] के फ़ंक्शंस हैं, जिनकी गणना [[मार्कोव एल्गोरिथ्म]] द्वारा की जा सकती है।
-मानों के साथ सभी कुल पुनरावर्ती कार्यों का उपसमूह {{math|{{mset|0,1}}}} को [[कम्प्यूटेशनल जटिलता सिद्धांत]] में [[आर (जटिलता)]] के रूप में जाना जाता है।
+मानों के साथ सभी टोटल रिकर्सिव फ़ंक्शन का उपसमूह {{math|{{mset|0,1}}}} को [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल काॅम्पलेक्सिटी थ्योरी]] में [[आर (जटिलता)|r (काॅम्पलेक्सिटी)]] के रूप में जाना जाता है।
 ==परिभाषा==
-μ-पुनरावर्ती कार्य (या सामान्य पुनरावर्ती कार्य) आंशिक कार्य हैं जो प्राकृतिक संख्याओं के सीमित टुपल्स लेते हैं और एकल प्राकृतिक संख्या लौटाते हैं। वे आंशिक फ़ंक्शंस का सबसे छोटा वर्ग हैं जिसमें प्रारंभिक फ़ंक्शंस शामिल हैं और संरचना, आदिम रिकर्सन और μ ऑपरेटर | न्यूनतमकरण ऑपरेटर के तहत बंद है {{mvar|μ}}.
+μ-रिकर्सिव फ़ंक्शन (या सामान्य रिकर्सिव फ़ंक्शन) पार्शियल फंक्शन हैं, जो प्राकृतिक संख्याओं के सीमित टपल्स लेते हैं और एकल प्राकृतिक संख्या लौटाते हैं। वे पार्शियल फंक्शन का सबसे छोटा वर्ग हैं, जिसमें प्रारंभिक फ़ंक्शंस सम्मिलित होते हैं और संरचना, स्यूडो रिकर्सन और μ ऑपरेटर या मिनिमाइजेशन ऑपरेटर {{mvar|μ}} के अनुसार विवृत है।
-प्रारंभिक कार्यों सहित कार्यों का सबसे छोटा वर्ग और संरचना और आदिम पुनरावर्तन के तहत बंद (अर्थात न्यूनतमकरण के बिना) [[आदिम पुनरावर्ती कार्य]]ों का वर्ग है। जबकि सभी आदिम पुनरावर्ती कार्य कुल हैं, यह आंशिक पुनरावर्ती कार्यों के लिए सच नहीं है; उदाहरण के लिए, उत्तराधिकारी फ़ंक्शन का न्यूनतमकरण अपरिभाषित है। आदिम पुनरावर्ती कार्य कुल पुनरावर्ती कार्यों का उपसमूह हैं, जो आंशिक पुनरावर्ती कार्यों का उपसमूह हैं। उदाहरण के लिए, एकरमैन फ़ंक्शन को पूर्ण पुनरावर्ती और गैर-आदिम साबित किया जा सकता है।
+प्रारंभिक कार्यों सहित कार्यों का सबसे छोटा वर्ग और संरचना और स्यूडो पुनरावर्तन के अनुसार विवृत (अर्थात मिनिमाइजेशन के अतिरिक्त) [[आदिम पुनरावर्ती कार्य|स्यूडो रिकर्सिव]] फ़ंक्शन का वर्ग है। जबकि सभी स्यूडो रिकर्सिव फ़ंक्शन यहाँ पर इसका कुल भाग हैं, यह पार्शियल रिकर्सिव फ़ंक्शन के लिए सत्य नहीं है, उदाहरण के लिए, सक्सेसर फंक्शन का मिनिमाइजेशन अपरिभाषित है। इसके आधार पर स्यूडो रिकर्सिव फ़ंक्शन टोटल रिकर्सिव फ़ंक्शन का उपसमूह हैं, जो पार्शियल रिकर्सिव फ़ंक्शन का उपसमूह हैं। उदाहरण के लिए, एकरमैन फ़ंक्शन को पूर्ण रिकर्सिव और गैर-स्यूडो प्रमाणित किया जा सकता है।
-आदिम या बुनियादी कार्य:
+स्यूडो या जनरल फंक्शन:
-#निरंतर कार्य {{mvar|C{{su|b=n|p=k}}}}: प्रत्येक प्राकृतिक संख्या के लिए {{mvar|n}} और हर {{mvar|k}}
+#काॅन्ट्यूनिटी फंक्शन {{mvar|C{{su|b=n|p=k}}}}: प्रत्येक प्राकृतिक संख्या के लिए {{mvar|n}} और हर का मान {{mvar|k}} हैं।
 #::<math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  n</math>
-#:वैकल्पिक परिभाषाएँ शून्य फ़ंक्शन का उपयोग आदिम फ़ंक्शन के रूप में करती हैं जो हमेशा शून्य लौटाता है, और शून्य फ़ंक्शन, उत्तराधिकारी फ़ंक्शन और कंपोज़िशन ऑपरेटर से निरंतर फ़ंक्शन का निर्माण करता है।
+#:वैकल्पिक परिभाषाएँ शून्य फ़ंक्शन का उपयोग स्यूडो फ़ंक्शन के रूप में करती हैं, जो सदैव शून्य लौटाता है, और शून्य फ़ंक्शन, सक्सेसर फंक्शन और कंपोज़िशन ऑपरेटर से काॅन्ट्यूनिटी फंक्शन का निर्माण करता है।
-# उत्तराधिकारी फ़ंक्शन एस:
+# सक्सेसर फंक्शन S:
 #::<math>S(x) \ \stackrel{\mathrm{def}}{=}\  x + 1\,</math>
-# प्रक्षेपण समारोह <math>P_i^k</math> (पहचान फ़ंक्शन भी कहा जाता है): सभी प्राकृतिक संख्याओं के लिए <math>i, k</math> ऐसा है कि <math>1\le i\le k</math>:
+# प्रोजेक्शन फंक्शन <math>P_i^k</math> (आइडेंटिकल फ़ंक्शन भी कहा जाता है): सभी प्राकृतिक संख्याओं के लिए <math>i, k</math> ऐसा है कि <math>1\le i\le k</math>:
 #::<math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\  x_i \, .</math>
-ऑपरेटर्स (ऑपरेटर द्वारा परिभाषित फ़ंक्शन का डोमेन तर्कों के मानों का सेट है, जैसे कि गणना के दौरान किया जाने वाला प्रत्येक फ़ंक्शन एप्लिकेशन अच्छी तरह से परिभाषित परिणाम प्रदान करता है):
+ऑपरेटर्स (ऑपरेटर द्वारा परिभाषित फ़ंक्शन का डोमेन तर्कों के मानों का सेट है, जैसे कि गणना के दौरान किया जाने वाला प्रत्येक फ़ंक्शन एप्लिकेशन को अच्छी तरह से परिभाषित करने के बाद उपयुक्त परिणाम प्रदान करता है):
-# रचना संचालक <math>\circ\,</math> (प्रतिस्थापन ऑपरेटर भी कहा जाता है): एम-एरी फ़ंक्शन दिया गया है <math>h(x_1,\ldots,x_m)\,</math> और एम के-एरी फ़ंक्शन <math>g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k)</math>:
+# कंपोजीशन आपरेटर <math>\circ\,</math> (प्रतिस्थापन ऑपरेटर भी कहा जाता है): एम-एरे फ़ंक्शन दिया गया है, इसके आधार पर <math>h(x_1,\ldots,x_m)\,</math> और एम के-ऐरे फंक्शन <math>g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k)</math>:
 #::<math>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)).</math>
-#:इस का मतलब है कि <math>f(x_1,\ldots,x_k)</math> केवल तभी परिभाषित किया गया है <math>g_1(x_1,\ldots,x_k),\ldots, g_m(x_1,\ldots,x_k),</math> और <math>h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k))</math> सभी परिभाषित हैं.
+#:इसका अर्थ है कि <math>f(x_1,\ldots,x_k)</math> केवल तभी परिभाषित किया गया है, इसके आधार पर <math>g_1(x_1,\ldots,x_k),\ldots, g_m(x_1,\ldots,x_k),</math> और <math>h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k))</math> सभी परिभाषित हैं।
-# आदिम रिकर्सन ऑपरेटर {{mvar|&rho;}}: k-ary फ़ंक्शन को देखते हुए <math>g(x_1,\ldots,x_k)\,</math> और k+2-एरी फ़ंक्शन <math>h(y,z,x_1,\ldots,x_k)\,</math>:
+# स्यूडो रिकर्सन ऑपरेटर {{mvar|&rho;}}: k-ary फ़ंक्शन को देखते हुए <math>g(x_1,\ldots,x_k)\,</math> और k+2-ऐरे फंक्शन <math>h(y,z,x_1,\ldots,x_k)\,</math>:
 #::<math>\begin{align}
               \rho(g, h) &\ \stackrel{\mathrm{def}}{=}\  f \quad\text{where the k+1 -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>
-#:इस का मतलब है कि <math>f(y,x_1,\ldots,x_k)</math> केवल तभी परिभाषित किया गया है <math>g(x_1,\ldots,x_k)</math> और <math>h(z,f(z,x_1,\ldots,x_k),x_1,\ldots,x_k)</math> सभी के लिए परिभाषित हैं <math>z<y.</math>
+#:इस का अर्थ है कि <math>f(y,x_1,\ldots,x_k)</math> केवल तभी परिभाषित किया गया है, <math>g(x_1,\ldots,x_k)</math> और <math>h(z,f(z,x_1,\ldots,x_k),x_1,\ldots,x_k)</math> सभी के लिए <math>z<y.</math> के अनुसार परिभाषित किया गया हैं।
-#न्यूनीकरण ऑपरेटर {{mvar|&mu;}}: (k+1)-एरी फ़ंक्शन दिया गया है <math>f(y, x_1, \ldots, x_k)\,</math>, के-एरी फ़ंक्शन <math>\mu(f)</math> द्वारा परिभाषित किया गया है:
+#मिनिमाइजेशन ऑपरेटर {{mvar|&mu;}}: (k+1)-ऐरे फंक्शन दिया गया है <math>f(y, x_1, \ldots, x_k)\,</math>, के-ऐरे फंक्शन <math>\mu(f)</math> द्वारा परिभाषित किया गया है:
 #::<math>\begin{align}
            \mu(f)(x_1, \ldots, x_k) = z \stackrel{\mathrm{def}}{\iff}\ f(i, x_1, \ldots, x_k)&>0 \quad \text{for}\quad i=0, \ldots, z-1 \quad\text{and}\\
           f(z, x_1, \ldots, x_k)&=0\quad
 \end{align}</math>
-सहज रूप से, न्यूनतमकरण खोजता है - 0 से खोज शुरू करना और ऊपर की ओर बढ़ना - सबसे छोटा तर्क जो फ़ंक्शन को शून्य पर लौटने का कारण बनता है; यदि ऐसा कोई तर्क नहीं है, या यदि कोई किसी तर्क का सामना करता है जिसके लिए {{mvar|f}} परिभाषित नहीं है, तो खोज कभी समाप्त नहीं होती, और <math> \mu(f)</math> तर्क के लिए परिभाषित नहीं है <math>(x_1, \ldots, x_k).</math>
+सहजता से, मिनिमाइजेशन खोजता है- इसके आधार पर 0 से खोज प्रारंभ करना और ऊपर की ओर बढ़ता हैं- इसका सबसे छोटा तर्क जो फ़ंक्शन को शून्य पर लौटने का कारण बनता है, यदि ऐसा कोई तर्क नहीं है, या यदि कोई किसी तर्क का सामना करता है जिसके लिए {{mvar|f}} परिभाषित नहीं है, तो खोज कभी समाप्त नहीं होती, और <math> \mu(f)</math> तर्क के लिए <math>(x_1, \ldots, x_k).</math> द्वारा परिभाषित नहीं करता है।
-जबकि कुछ पाठ्यपुस्तकें μ-ऑपरेटर का उपयोग करती हैं जैसा कि यहां परिभाषित है,<ref name="Enderton.1972">Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972</ref><ref name="Boolos.Burgess.Jeffrey.2007">Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007</ref> दूसरों को पसंद है<ref name="Jones.1997">Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997</ref><ref>Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982</ref> मांग करें कि μ-ऑपरेटर को कुल कार्यों पर लागू किया जाए {{mvar|f}} केवल। यद्यपि यह यहां दी गई परिभाषा की तुलना में μ-ऑपरेटर को प्रतिबंधित करता है, μ-पुनरावर्ती कार्यों का वर्ग वही रहता है, जो क्लेन के सामान्य फॉर्म प्रमेय (# सामान्य फॉर्म प्रमेय देखें) से अनुसरण करता है।<ref name="Enderton.1972"/><ref name="Boolos.Burgess.Jeffrey.2007"/>एकमात्र अंतर यह है कि यह अनिर्णीत हो जाता है कि क्या विशिष्ट फ़ंक्शन परिभाषा μ-पुनरावर्ती फ़ंक्शन को परिभाषित करती है, क्योंकि यह अनिर्णीत है कि क्या गणना योग्य (यानी μ-पुनरावर्ती) फ़ंक्शन कुल है।<ref name="Jones.1997"/>
-[[मजबूत समानता]] ऑपरेटर <math>\simeq</math> आंशिक μ-पुनरावर्ती कार्यों की तुलना करने के लिए उपयोग किया जा सकता है। इसे सभी आंशिक फलनों f और g के लिए परिभाषित किया गया है
+जबकि कुछ लाइब्रेरी में μ-ऑपरेटर का उपयोग किया जाता हैं, जैसा कि यहां परिभाषित किया गया है,<ref name="Enderton.1972">Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972</ref><ref name="Boolos.Burgess.Jeffrey.2007">Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007</ref> यह मान इसके अतिरिक्त उपयोग किया जा सकता है।<ref name="Jones.1997">Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997</ref><ref>Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982</ref> यहाँ पर μ-ऑपरेटर को टोटल फंक्शन पर {{mvar|f}}  के द्वारा लागू किया जाता हैं। यद्यपि यह यहां दी गई परिभाषा की तुलना में μ-ऑपरेटर को प्रतिबंधित करता है, इसका μ-रिकर्सिव फ़ंक्शन का वर्ग समान रहता है, जो क्लेन के सामान्य फॉर्म प्रमेय (सामान्य फॉर्म प्रमेय देखें) जिससे इसका अनुसरण करते हैं।<ref name="Enderton.1972" /><ref name="Boolos.Burgess.Jeffrey.2007" /> इस प्रकार इसका एकमात्र अंतर यह है कि यह अनिर्णीत को प्रदान करता है कि क्या विशिष्ट फ़ंक्शन परिभाषा μ-रिकर्सिव फ़ंक्शन को परिभाषित करती है, क्योंकि यह अनिर्णीत है कि क्या गणना योग्य (अर्ताथ μ-रिकर्सिव) फ़ंक्शन कुल है।<ref name="Jones.1997" />
-:<math>f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l)</math> यदि और केवल तभी मान्य है जब तर्कों के किसी भी विकल्प के लिए या तो दोनों फ़ंक्शन परिभाषित हैं और उनके मान समान हैं या दोनों फ़ंक्शन अपरिभाषित हैं।
+[[मजबूत समानता|स्ट्रांग इक्ववैलिटी]] ऑपरेटर <math>\simeq</math> पार्शियल μ-रिकर्सिव फ़ंक्शन की तुलना करने के लिए उपयोग किया जा सकता है। इसे सभी आंशिक फलनों f और g के लिए परिभाषित किया गया है।
+:<math>f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l)</math> यदि और केवल तभी मान्य है, जब तर्कों के किसी भी विकल्प के लिए या तो दोनों फ़ंक्शन परिभाषित हैं और उनके मान समान हैं या दोनों फ़ंक्शन अपरिभाषित हैं।
 ==उदाहरण==
-मिनिमाइज़ेशन ऑपरेटर को शामिल न करने वाले उदाहरण आदिम पुनरावर्ती फ़ंक्शन#उदाहरण पर पाए जा सकते हैं।
+मिनिमाइज़ेशन ऑपरेटर को सम्मिलित न करने वाले उदाहरण स्यूडो रिकर्सिव फ़ंक्शन उदाहरण पर पाए जा सकते हैं।
-निम्नलिखित उदाहरणों का उद्देश्य केवल न्यूनतमकरण ऑपरेटर के उपयोग को प्रदर्शित करना है; उन्हें इसके बिना भी परिभाषित किया जा सकता है, यद्यपि अधिक जटिल तरीके से, क्योंकि वे सभी आदिम पुनरावर्ती हैं।
+निम्नलिखित उदाहरणों का उद्देश्य केवल मिनिमाइजेशन ऑपरेटर के उपयोग को प्रदर्शित करना है, उन्हें इसके बिना भी परिभाषित किया जा सकता है, यद्यपि अधिक काॅम्प्लेक्स प्रोसेस से, क्योंकि वे सभी स्यूडो रिकर्सिव हैं।
 {{unordered list
-|The [[integer square root]] of {{mvar|x}} can be defined as the least {{mvar|z}} such that <math>(z+1)^2 > x</math>. Using the minimization operator, a general recursive definition is <math>\operatorname{Isqrt} = \mu(\operatorname{Not} \circ \operatorname{Gt} \circ (\operatorname{Mul} \circ (S \circ P_1^2,S \circ P_1^2), P_2^2))</math>, where {{math|Not}}, {{math|Gt}}, and {{math|Mul}} are [[logical negation]], greater-than, and multiplication,<ref>defined in [[Primitive recursive function#Junctors]], [[Primitive recursive function#Equality predicate]], and [[Primitive recursive function#Multiplication]]</ref> respectively. In fact, <math>(\operatorname{Not} \circ \operatorname{Gt} \circ (\operatorname{Mul} \circ (S \circ P_1^2,S \circ P_1^2), P_2^2)) \; (z,x) = (\lnot S(z)*S(z) > x)</math> is {{val|0}} if, and only if, <math>S(z)*S(z) > x</math> holds. Hence <math>\operatorname{Isqrt}(x)</math> is the least {{mvar|z}} such that <math>S(z)*S(z) > x</math> holds. The negation [[junctor]] {{math|Not}} is needed since {{math|Gt}} encodes truth by {{val|1}}, while {{mvar|&mu;}} seeks for {{val|0}}.
+|[[पूर्णांक वर्गमूल]] का {{mvar|x}} न्यूनतम {{mvar|z}} के रूप में परिभाषित किया जा सकता है, इस प्रकार यह मान इस प्रकार है कि <math>(z+1)^2 > x</math> न्यूनतमकरण ऑपरेटर का उपयोग करते हुए, एक सामान्य पुनरावर्ती परिभाषा है <math>\operatorname{Isqrt} = \mu(\operatorname{Not} \circ \operatorname{Gt} \circ (\operatorname{Mul} \circ (S \circ P_1^2,S \circ P_1^2), P_2^2))</math>, जहाँ {{math|Not}}, {{math|Gt}}, and {{math|Mul}} [[लाॅजिकल निगेशन]], इससे बड़ा, और गुणा,<ref>defined in [[Primitive recursive function#Junctors]], [[Primitive recursive function#Equality predicate]], and [[Primitive recursive function#Multiplication]]</ref> वास्तविकता में, <math>(\operatorname{Not} \circ \operatorname{Gt} \circ (\operatorname{Mul} \circ (S \circ P_1^2,S \circ P_1^2), P_2^2)) \; (z,x) = (\lnot S(z)*S(z) > x)</math> is {{val|0}} यदि <math>S(z)*S(z) > x</math> उपयोग करता हैं। जहाँ पर <math>\operatorname{Isqrt}(x)</math> is the least {{mvar|z}} जिसके लिए <math>S(z)*S(z) > x</math> उपयोग करता हैँ। निषेध [[जंक्टर]] {{math|Not}} से आवश्यकता है{{math|Gt}} सत्य को एन्कोड करता है, {{val|1}}, जबकि {{mvar|&mu;}} {{val|0}} ढूंढता है।
 }}
-निम्नलिखित उदाहरण सामान्य पुनरावर्ती कार्यों को परिभाषित करते हैं जो आदिम पुनरावर्ती नहीं हैं; इसलिए वे न्यूनतमकरण ऑपरेटर का उपयोग करने से बच नहीं सकते।
+निम्नलिखित उदाहरण सामान्य रिकर्सिव फ़ंक्शन को परिभाषित करते हैं जो स्यूडो रिकर्सिव नहीं हैं, इसलिए वे मिनिमाइजेशन ऑपरेटर का उपयोग करने से बच नहीं सकते हैं।
-== कुल पुनरावर्ती फ़ंक्शन ==
+== टोटल रिकर्सिव फ़ंक्शन ==
-एक सामान्य पुनरावर्ती फ़ंक्शन को कुल पुनरावर्ती फ़ंक्शन कहा जाता है यदि इसे प्रत्येक इनपुट के लिए परिभाषित किया गया है, या, समकक्ष, यदि इसकी गणना [[कुल ट्यूरिंग मशीन]] द्वारा की जा सकती है। गणनात्मक रूप से यह बताने का कोई तरीका नहीं है कि दिया गया सामान्य पुनरावर्ती कार्य पूर्ण है या नहीं - ''हॉल्टिंग समस्या'' देखें।
+यह ऐसा जनरल रिकर्सिव फंक्शन हैं, जिसको टोटल रिकर्सिव फ़ंक्शन कहा जाता है, यदि इसे प्रत्येक इनपुट के लिए परिभाषित किया गया है, या समकक्ष, यदि इसकी गणना [[कुल ट्यूरिंग मशीन]] द्वारा की जा सकती है। गणनात्मक रूप से यह बताने की कोई विधि नहीं है, कि दिया गया सामान्य रिकर्सिव फ़ंक्शन पूर्ण है या नहीं ''हॉल्टिंग समस्या'' देखें।
 == संगणना के अन्य मॉडलों के साथ समतुल्यता ==
-चर्च की थीसिस में, ट्यूरिंग मशीनों के बीच समानांतर रेखा खींची जाती है जो कुछ इनपुट के लिए समाप्त नहीं होती है और संबंधित आंशिक पुनरावर्ती फ़ंक्शन में उस इनपुट के लिए अपरिभाषित परिणाम होता है।
+चर्च की इस थीसिस में, ट्यूरिंग मशीनों के बीच समानांतर रेखा खींची जाती है जो कुछ इनपुट के लिए समाप्त नहीं होती है और संबंधित पार्शियल रिकर्सिव फंक्शन में उस इनपुट के लिए अपरिभाषित परिणाम होता है।
-अनबाउंड सर्च ऑपरेटर आदिम रिकर्सन के नियमों द्वारा परिभाषित नहीं है क्योंकि वे अनंत लूप (अपरिभाषित मान) के लिए तंत्र प्रदान नहीं करते हैं।
+अनबाउंड सर्च ऑपरेटर स्यूडो रिकर्सन के नियमों द्वारा परिभाषित नहीं है क्योंकि वे इनफाइनाइट लूप (अपरिभाषित मान) के लिए सिस्टम प्रदान नहीं करते हैं।
+== सामान्य रूपी प्रमेय ==
-== सामान्य रूप प्रमेय ==
+क्लेन का t विधेय क्लीन के कारण सामान्य रूप प्रमेय कहता है कि प्रत्येक k के लिए स्यूडो रिकर्सिव फ़ंक्शन <math>U(y)\!</math> और <math>T(y,e,x_1,\ldots,x_k)\!</math>  हैं। यह इस प्रकार हैं कि किसी भी μ-रिकर्सिव फ़ंक्शन के लिए <math>f(x_1,\ldots,x_k)\!</math> k मुक्त चर के साथ e ऐसा है-
+:<math>f(x_1,\ldots,x_k) \simeq U(\mu(T)(e,x_1,\ldots,x_k))</math>
+फ़ंक्शन f के लिए संख्या e को इंडेक्स या गोडेल नंबर कहा जाता है।<ref>{{cite journal | doi=10.1090/S0002-9947-1943-0007371-8 | url=https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf | author=Stephen Cole Kleene | title=पुनरावर्ती विधेय और परिमाणक| journal=Transactions of the American Mathematical Society | volume=53 | number=1 | pages=41&ndash;73 | date=Jan 1943 | doi-access=free }}</ref>{{rp|52–53}} इस परिणाम का परिणाम यह है कि किसी भी μ-रिकर्सिव फ़ंक्शन को (कुल) स्यूडो रिकर्सिव फ़ंक्शन पर लागू μ ऑपरेटर के एकल उदाहरण का उपयोग करके परिभाषित किया जा सकता है।
-क्लेन का टी विधेय#क्लीन के कारण सामान्य रूप प्रमेय कहता है कि प्रत्येक k के लिए आदिम पुनरावर्ती कार्य हैं <math>U(y)\!</math> और <math>T(y,e,x_1,\ldots,x_k)\!</math> ऐसा कि किसी भी μ-पुनरावर्ती फ़ंक्शन के लिए <math>f(x_1,\ldots,x_k)\!</math> k मुक्त चर के साथ e ऐसा है
+[[मार्विन मिंस्की]] इसका निरीक्षण करते हैं <math>U</math> ऊपर परिभाषित संक्षेप में सार्वभौमिक ट्यूरिंग मशीन के μ-रिकर्सिव समकक्ष है:
-:<math>f(x_1,\ldots,x_k) \simeq U(\mu(T)(e,x_1,\ldots,x_k))</math>.
-फ़ंक्शन f के लिए संख्या e को इंडेक्स या गोडेल नंबर कहा जाता है।<ref>{{cite journal | doi=10.1090/S0002-9947-1943-0007371-8 | url=https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf | author=Stephen Cole Kleene | title=पुनरावर्ती विधेय और परिमाणक| journal=Transactions of the American Mathematical Society | volume=53 | number=1 | pages=41&ndash;73 | date=Jan 1943 | doi-access=free }}</ref>{{rp|52–53}} इस परिणाम का परिणाम यह है कि किसी भी μ-पुनरावर्ती फ़ंक्शन को (कुल) आदिम पुनरावर्ती फ़ंक्शन पर लागू μ ऑपरेटर के एकल उदाहरण का उपयोग करके परिभाषित किया जा सकता है।
-[[मार्विन मिंस्की]] इसका निरीक्षण करते हैं <math>U</math> ऊपर परिभाषित संक्षेप में सार्वभौमिक ट्यूरिंग मशीन के μ-पुनरावर्ती समकक्ष है:
+{{blockquote |text=यू का निर्माण करने के लिए एक सामान्य-पुनरावर्ती फ़ंक्शन यू (एन, एक्स) की परिभाषा लिखना है जो संख्या एन की सही व्याख्या करता है और एक्स के उचित फ़ंक्शन की गणना करता है। यू को सीधे बनाने में अनिवार्य रूप से उतना ही प्रयास, ''और मूल रूप से वही विचार'' शामिल होंगे, जितना हमने यूनिवर्सल ट्यूरिंग मशीन के निर्माण में निवेश किया है। {{sfn|Minsky|1972|pp=189}}}}
-{{blockquote |text=To construct U is to write down the definition of a general-recursive function U(n, x) that correctly interprets the number n and computes the appropriate function of x. to construct U directly would involve essentially the same amount of effort, ''and essentially the same ideas'', as we have invested in constructing the universal Turing machine {{sfn|Minsky|1972|pp=189}}}}
 == प्रतीकवाद ==
-साहित्य में अनेक प्रकार के प्रतीकों का प्रयोग किया जाता है। प्रतीकवाद का उपयोग करने का फायदा यह है कि ऑपरेटरों को के अंदर करके फ़ंक्शन की व्युत्पत्ति की जाती है, जिसे कॉम्पैक्ट रूप में लिखना आसान होता है। निम्नलिखित में पैरामीटर्स की स्ट्रिंग x<sub>1</sub>, ..., एक्स<sub>n</sub> इसे x के रूप में संक्षिप्त किया गया है:
+साहित्य में अनेक प्रकार के प्रतीकों का प्रयोग किया जाता है। प्रतीकवाद का उपयोग करने का फायदा यह है कि ऑपरेटरों को के अंदर करके फ़ंक्शन की व्युत्पत्ति की जाती है, जिसे कॉम्पैक्ट रूप में लिखना सरल होता है। निम्नलिखित में पैरामीटर्स की स्ट्रिंग x<sub>1</sub>, ..., x<sub>n</sub> इसे x के रूप में संक्षिप्त किया गया है:
-* ''निरंतर कार्य'': क्लेन सी का उपयोग करता है{{su|b=q|p=n}}(x) = q और बूलोस-बर्गेस-जेफरी (2002) (बी-बी-जे) संक्षिप्त नाम const का उपयोग करते हैं<sub>n</sub>( एक्स) = एन :
+* ''काॅन्ट्यूनिटी फंक्शन'': क्लेन c{{su|b=q|p=n}}(x) = q का उपयोग करता है, और बूलोस-बर्गेस-जेफरी (2002) (b-b-j) संक्षिप्त नाम const<sub>n</sub>( x) = n  का उपयोग करते हैं:
-:: उदा. सी{{su|b=13|p=7}} (आर, एस, टी, यू, वी, डब्ल्यू, एक्स) = 13
+:: उदाहरण के लिए c{{su|b=13|p=7}} (r, s, t, u, v, w, x) = 13
-:: उदा. कॉन्स्ट<sub>13</sub> (आर, एस, टी, यू, वी, डब्ल्यू, एक्स) = 13
+:: उदा. const<sub>13</sub> (r, s, t, u, v, w, x) = 13
-* उत्तराधिकारी फ़ंक्शन: क्लेन उत्तराधिकारी के लिए x' और S का उपयोग करता है। चूंकि उत्तराधिकारी को आदिम माना जाता है, अधिकांश ग्रंथ एपॉस्ट्रॉफ़ी का उपयोग इस प्रकार करते हैं:
+* सक्सेसर फंक्शन: क्लेन सक्सेसर के लिए x' और S का उपयोग करता है। चूंकि सक्सेसर को स्यूडो माना जाता है, अधिकांश ग्रंथ एपॉस्ट्रॉफ़ी का उपयोग इस प्रकार करते हैं:
-:: एस(ए) = ए +1 =<sub>def</sub> ए', जहां 1 =<sub>def</sub> 0', 2 =<sub>def</sub> 0 '', आदि।
+:: s(a) = a +1 =<sub>def</sub> a', जहां 1 =<sub>def</sub> 0', 2 =<sub>def</sub> 0 '', आदि।
-* पहचान फ़ंक्शन: क्लेन (1952) यू का उपयोग करता है{{su|b=i|p=n}} वेरिएबल x पर पहचान फ़ंक्शन को इंगित करने के लिए<sub>i</sub>; बी-बी-जे पहचान फ़ंक्शन आईडी का उपयोग करें{{su|b=i|p=n}} चर x पर<sub>1</sub> एक्स को<sub>n</sub>:
+* आइडेंटिटी फंक्शन: क्लेन (1952) u{{su|b=i|p=n}} का उपयोग करता है वेरिएबल x<sub>i</sub> पर आइडेंटिटी फंक्शन को इंगित करने के लिए, b-b-j{{su|b=i|p=n}} चर x<sub>1</sub> पर x<sub>n</sub> को आइडेंटिटी फंक्शन id का उपयोग करें:
-: यू{{su|b=i|p=n}}( एक्स ) = आईडी{{su|b=i|p=n}}( एक्स ) = एक्स<sub>i</sub> : जैसे यू{{su|b=3|p=7}} = आईडी{{su|b=3|p=7}} (आर, एस, टी, यू, वी, डब्ल्यू, एक्स) = टी
+: u{{su|b=i|p=n}}( x ) = id{{su|b=i|p=n}}( x ) = x<sub>i</sub> : जैसे u{{su|b=3|p=7}} = id{{su|b=3|p=7}} (r, s, t, u, v, w, x) = t
-* रचना (प्रतिस्थापन) ऑपरेटर: क्लेन बोल्ड-फेस 'एस' का उपयोग करता है{{su|b=n|p=m}} (उसके उत्तराधिकारी के साथ भ्रमित न हों!)। सुपरस्क्रिप्ट m, m को संदर्भित करता है<sup>फ़ंक्शन f का वें</sup><sub>m</sub>, जबकि सबस्क्रिप्ट n, n को संदर्भित करता है<sup>वें</sup>वेरिएबल x<sub>n</sub>:
+* रचना (प्रतिस्थापन) ऑपरेटर: क्लेन बोल्ड-फेस 's'{{su|b=n|p=m}} का उपयोग करता है, उसके सक्सेसर के साथ भ्रमित न हों!। इस प्रकार सुपरस्क्रिप्ट m, m<sup>f</sup><sub>m</sub> को संदर्भित करता है, जबकि इस प्रकार सबस्क्रिप्ट n, n वेरिएबल x<sub>n</sub> को संदर्भित करता है :
-:यदि हमें h(x)=g(f) दिया गया है<sub>1</sub>(एक्स), ..., एफ<sub>m</sub>(एक्स) )
+:यदि हमें h(x)=g(f) दिया गया है<sub>1</sub>(x), ..., f<sub>m</sub>(x) )
-:: एच(एक्स) = एस{{su|b=m|p=n}}(जी, एफ<sub>1</sub>, ... , एफ<sub>m</sub> )
+:: h(x) = s{{su|b=m|p=n}}(g, f<sub>1</sub>, ... , f<sub>m</sub> )
-:इसी तरह, लेकिन उप- और सुपरस्क्रिप्ट के बिना, बी-बी-जे लिखते हैं:
+:इसी प्रकार, उप- और सुपरस्क्रिप्ट के बिना, b-b-j लिखते हैं:
-:: h(x')= Cn[g, f<sub>1</sub> ,..., एफ<sub>m</sub>](एक्स)
+:: h(x')= Cn[g, f<sub>1</sub> ,..., f<sub>m</sub>](x)
-* ''आदिम पुनरावर्तन'': क्लेन प्रतीक आर का उपयोग करता है<sup>n</sup>(बेस स्टेप, इंडक्शन स्टेप) जहां n वेरिएबल्स की संख्या को इंगित करता है, बी-बी-जे Pr(बेस स्टेप, इंडक्शन स्टेप)(x) का उपयोग करते हैं। दिया गया:
+* ''स्यूडो पुनरावर्तन'': क्लेन प्रतीक r<sup>n</sup> का उपयोग करता है(बेस स्टेप, इंडक्शन स्टेप) जहां n वेरिएबल्स की संख्या को इंगित करता है, इस प्रकार b-b-j Pr(बेस स्टेप, इंडक्शन स्टेप)(x) का उपयोग करते हैं। जो इस प्रकार दिया गया हैं:
 :* आधार चरण: h( 0, x )= f( x ), और
 :* प्रेरण चरण: h( y+1, x ) = g( y, h(y, x),x )
-: उदाहरण: ए + बी की आदिम रिकर्सन परिभाषा:
+: उदाहरण: a + b का स्यूडो रिकर्सन परिभाषा:
-::* आधार चरण: f( 0, a ) = a = U{{su|b=1|p=1}}(ए)
+::* आधार चरण: f( 0, a ) = a = U{{su|b=1|p=1}}(a)
-::* प्रेरण चरण: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U{{su|b=2|p=3}}(बी, सी, ए))
+::* प्रेरण चरण: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U{{su|b=2|p=3}}(b, c, a))
-::: आर<sup>2</sup>{ यू{{su|b=1|p=1}}(a), S [ (U{{su|b=2|p=3}}( b, c, a ) ] }
+::: r<sup>2</sup>{ u{{su|b=1|p=1}}(a), S [ (U{{su|b=2|p=3}}( b, c, a ) ] }
-::: पर{ ु{{su|b=1|p=1}}(ए), एस[(यू{{su|b=2|p=3}}(बी, सी, ए) ] }
+::: {u{{su|b=1|p=1}}(a), s[(u{{su|b=2|p=3}}(b, c, a) ] }
-उदाहरण: क्लेन उदाहरण देता है कि f(b, a) = b + a की पुनरावर्ती व्युत्पत्ति कैसे करें (वेरिएबल a और b का उलटा नोटिस)। वह 3 प्रारंभिक कार्यों से प्रारंभ करता है
+उदाहरण: क्लेन उदाहरण देता है कि f(b, a) = b + a की रिकर्सिव व्युत्पत्ति वेरिएबल a और b की व्युत्क्रम नोटिस को कैसे करें। वह 3 प्रारंभिक कार्यों से प्रारंभ करता है
-:# एस(ए) = ए'
+:# s(a) = a'
-:# यू{{su|b=1|p=1}}(ए) = ए
+:# u{{su|b=1|p=1}}(a) = a
-:# यू{{su|b=2|p=3}}(बी, सी, ए) = सी
+:# u{{su|b=2|p=3}}(b, c, a) = c
-:# जी(बी, सी, ए) = एस(यू{{su|b=2|p=3}}(बी, सी, ए)) = सी'
+:# g(b, c, a) = s(u{{su|b=2|p=3}}(b, c, a)) = c'
-:# आधार चरण: h( 0, a ) = U{{su|b=1|p=1}}(ए)
+:# आधार चरण: h( 0, a ) = U{{su|b=1|p=1}}(a)
-:: प्रेरण चरण: एच(बी', ए) = जी(बी, एच(बी, ए), ए)
+:: प्रेरण चरण: h(b', a) = g(b, h(b, a), a)
 वह यहां पहुंचता है:
-:: ए+बी = आर<sup>2</sup>[यू{{su|b=1|p=1}}, एस{{su|b=1|p=3}}(एस, यू{{su|b=2|p=3}}) ]
+:: a+b = r<sup>2</sup>[u{{su|b=1|p=1}}, s{{su|b=1|p=3}}(s, u{{su|b=2|p=3}}) ]
 ==उदाहरण==
-* [[फाइबोनैचि संख्या]]
+* [[फाइबोनैचि संख्या|फाइबोनैचि नंबर]]
 * [[मैक्कार्थी 91 फ़ंक्शन]]
 ==यह भी देखें==
-*पुनरावृत्ति सिद्धांत
+*रिकर्सन थ्योरी
-* [[प्रत्यावर्तन]]
+* [[प्रत्यावर्तन|रिकर्सन]]
 * [[रिकर्सन (कंप्यूटर विज्ञान)]]

Anonymous

Search

जनरल रिकर्सिव फंक्शन: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:22, 9 August 2023

Contents

परिभाषा

उदाहरण

टोटल रिकर्सिव फ़ंक्शन

संगणना के अन्य मॉडलों के साथ समतुल्यता

सामान्य रूपी प्रमेय

प्रतीकवाद

उदाहरण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

जनरल रिकर्सिव फंक्शन: Difference between revisions

Revision as of 11:22, 9 August 2023

परिभाषा

उदाहरण

टोटल रिकर्सिव फ़ंक्शन

संगणना के अन्य मॉडलों के साथ समतुल्यता

सामान्य रूपी प्रमेय

प्रतीकवाद

उदाहरण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories