जनरल रिकर्सिव फंक्शन

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

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

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

परिभाषा

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

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

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

1. काॅन्ट्यूनिटी फंक्शन C^k
   _n: प्रत्येक प्राकृतिक संख्या के लिए n और हर का मान k हैं।

   $C_{n}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ n$

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

2. सक्सेसर फंक्शन S:

   $S(x)\ {\stackrel {\mathrm {def} }{=}}\ x+1\,$

3. प्रोजेक्शन फंक्शन $P_{i}^{k}$ (आइडेंटिकल फ़ंक्शन भी कहा जाता है): सभी प्राकृतिक संख्याओं के लिए $i,k$ ऐसा है कि $1\leq i\leq k$:

   $P_{i}^{k}(x_{1},\ldots ,x_{k})\ {\stackrel {\mathrm {def} }{=}}\ x_{i}\,.$

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

1. कंपोजीशन आपरेटर $\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}))$ सभी परिभाषित हैं।

2. स्यूडो रिकर्सन ऑपरेटर ρ: 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.$ के अनुसार परिभाषित किया गया हैं।

3. मिनिमाइजेशन ऑपरेटर μ: (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}).$ द्वारा परिभाषित नहीं करता है।

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

स्ट्रांग इक्ववैलिटी ऑपरेटर $\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 लाॅजिकल निगेशन, इससे बड़ा, और गुणा, वास्तविकता में, $(\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 को इंडेक्स या गोडेल नंबर कहा जाता है। इस परिणाम का परिणाम यह है कि किसी भी μ-रिकर्सिव फ़ंक्शन को (कुल) स्यूडो रिकर्सिव फ़ंक्शन पर लागू μ ऑपरेटर के एकल उदाहरण का उपयोग करके परिभाषित किया जा सकता है।

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

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

प्रतीकवाद

साहित्य में अनेक प्रकार के प्रतीकों का प्रयोग किया जाता है। प्रतीकवाद का उपयोग करने का फायदा यह है कि ऑपरेटरों को के अंदर करके फ़ंक्शन की व्युत्पत्ति की जाती है, जिसे कॉम्पैक्ट रूप में लिखना सरल होता है। निम्नलिखित में पैरामीटर्स की स्ट्रिंग 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 प्रारंभिक कार्यों से प्रारंभ करता है

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

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

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

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

उदाहरण

• फाइबोनैचि नंबर
• मैक्कार्थी 91 फ़ंक्शन

यह भी देखें

• रिकर्सन थ्योरी
• रिकर्सन
• रिकर्सन (कंप्यूटर विज्ञान)

संदर्भ

• 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.

बाहरी संबंध

• Stanford Encyclopedia of Philosophy entry
• A compiler for transforming a recursive function into an equivalent Turing machine