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

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

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

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

परिभाषा

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

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

आदिम या बुनियादी कार्य:

1. निरंतर कार्य C^k
   _n: प्रत्येक प्राकृतिक संख्या के लिए n और हर k

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

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

2. उत्तराधिकारी फ़ंक्शन एस:

   $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})$ यदि और केवल तभी मान्य है जब तर्कों के किसी भी विकल्प के लिए या तो दोनों फ़ंक्शन परिभाषित हैं और उनके मान समान हैं या दोनों फ़ंक्शन अपरिभाषित हैं।

उदाहरण

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

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

• The integer square root of x can be defined as the least z such that $(z+1)^{2}>x$. Using the minimization operator, a general recursive definition is $\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}))$, where Not, Gt, and Mul are logical negation, greater-than, and multiplication, respectively. In fact, $(\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 if, and only if, $S(z)*S(z)>x$ holds. Hence $\operatorname {Isqrt} (x)$ is the least z such that $S(z)*S(z)>x$ holds. The negation junctor Not is needed since Gt encodes truth by 1, while μ seeks for 0.

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

कुल पुनरावर्ती फ़ंक्शन

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

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

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

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

क्लेन का टी विधेय#क्लीन के कारण सामान्य रूप प्रमेय कहता है कि प्रत्येक 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$ ऊपर परिभाषित संक्षेप में सार्वभौमिक ट्यूरिंग मशीन के μ-पुनरावर्ती समकक्ष है:

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

प्रतीकवाद

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

• निरंतर कार्य: क्लेन सी का उपयोग करता हैⁿ
  _q(x) = q और बूलोस-बर्गेस-जेफरी (2002) (बी-बी-जे) संक्षिप्त नाम const का उपयोग करते हैं_n( एक्स) = एन :

उदा. सी⁷
₁₃ (आर, एस, टी, यू, वी, डब्ल्यू, एक्स) = 13

उदा. कॉन्स्ट₁₃ (आर, एस, टी, यू, वी, डब्ल्यू, एक्स) = 13

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

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

• पहचान फ़ंक्शन: क्लेन (1952) यू का उपयोग करता हैⁿ
  _i वेरिएबल x पर पहचान फ़ंक्शन को इंगित करने के लिए_i; बी-बी-जे पहचान फ़ंक्शन आईडी का उपयोग करेंⁿ
  _i चर x पर₁ एक्स को_n:

यूⁿ
_i( एक्स ) = आईडीⁿ
_i( एक्स ) = एक्स_i : जैसे यू⁷
₃ = आईडी⁷
₃ (आर, एस, टी, यू, वी, डब्ल्यू, एक्स) = टी

• रचना (प्रतिस्थापन) ऑपरेटर: क्लेन बोल्ड-फेस 'एस' का उपयोग करता है^m
  _n (उसके उत्तराधिकारी के साथ भ्रमित न हों!)। सुपरस्क्रिप्ट m, m को संदर्भित करता है^{फ़ंक्शन f का वें}_m, जबकि सबस्क्रिप्ट n, n को संदर्भित करता है^वेंवेरिएबल x_n:

यदि हमें h(x)=g(f) दिया गया है₁(एक्स), ..., एफ_m(एक्स) )

एच(एक्स) = एसⁿ
_m(जी, एफ₁, ... , एफ_m )

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

h(x')= Cn[g, f₁ ,..., एफ_m](एक्स)

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

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

उदाहरण: ए + बी की आदिम रिकर्सन परिभाषा:

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

आर²{ यू¹
₁(a), S [ (U³
₂( b, c, a ) ] }

पर{ ु¹
₁(ए), एस[(यू³
₂(बी, सी, ए) ] }

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

1. एस(ए) = ए'
2. यू¹
   ₁(ए) = ए
3. यू³
   ₂(बी, सी, ए) = सी
4. जी(बी, सी, ए) = एस(यू³
   ₂(बी, सी, ए)) = सी'
5. आधार चरण: h( 0, a ) = 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