Μ ऑपरेटर: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Tag: Manual revert
 
(12 intermediate revisions by 3 users not shown)
Line 1: Line 1:
रिकर्सन सिद्धांत में, '''μ-संचालक''', न्यूनतम संचालक, या असीम खोज संचालक किसी दिए गए गुण के साथ सबसे कम [[प्राकृतिक संख्या]] की खोज करता है। [[आदिम पुनरावर्ती कार्य]] में μ-संचालक को जोड़ने से सभी [[गणना योग्य कार्य]] को परिभाषित करना संभव हो जाता है।
रिकर्सन सिद्धांत में, '''μ-संचालक''', न्यूनतम संचालक, या असीम अविष्कार संचालक किसी दिए गए गुण के साथ सबसे कम [[प्राकृतिक संख्या]] की अविष्कार करता है। [[आदिम पुनरावर्ती कार्य|प्रारंभिक पुनरावर्ती फलन]] में μ-संचालक को जोड़ने से सभी [[गणना योग्य कार्य|गणना योग्य]] फलन को परिभाषित करना संभव हो जाता है।


== परिभाषा ==
== परिभाषा ==
मान लीजिए कि R(y, x<sub>1</sub>, ..., एक्स<sub>''k''</sub>) [[प्राकृतिक संख्या]]ओं पर एक निश्चित (k+1)-एरी संबंध है। μ-संचालक μy, या तो असंबद्ध या परिबद्ध रूप में, प्राकृतिक संख्याओं से प्राकृतिक संख्याओं तक परिभाषित एक संख्या सिद्धांतिक फलन है। चूँकि, μy में प्राकृतिक संख्याओं पर एक [[विधेय (गणित)]] सम्मिलित है, जिसे एक ऐसी स्थिति के रूप में माना जा सकता है जो विधेय संतुष्ट होने पर सत्य और ऐसा नहीं होने पर गलत का मूल्यांकन करती है।
मान लीजिए कि R(y, x<sub>1</sub>, ..., x<sub>''k''</sub>) [[प्राकृतिक संख्या]]ओं पर निश्चित (k+1)-एरी संबंध है। μ-संचालक "μy", असंबद्ध या परिबद्ध रूप में, "अंकगणितीय फलन" है जो प्राकृतिक संख्याओं से प्राकृतिक संख्याओं तक की परिभाषा की जाती है। चूँकि, "μy" में प्राकृतिक संख्याओं पर [[विधेय (गणित)]] सम्मिलित है, जिसे ऐसी स्थिति के रूप में माना जा सकता है जो विधेय संतुष्ट होने पर सत्य और ऐसा नहीं होने पर गलत का मूल्यांकन करती है।


घिरे μ-संचालक पहले क्लेन (1952) अध्याय IX आदिम पुनरावर्ती कार्यों में दिखाई देता है, §45 विधेय, मुख्य कारक प्रतिनिधित्व इस प्रकार है:
घिरे μ-संचालक पहले क्लेन (1952) अध्याय IX प्रारंभिक पुनरावर्ती फलन में दिखाई देता है, §45 विधेय, मुख्य कारक प्रतिनिधित्व इस प्रकार है:
:<math>\mu y_{y<z} R(y). \ \ \mbox{The least} \ y<z \ \mbox{such that} \ R(y), \ \mbox{if} \ (\exists y)_{y<z} R(y); \ \mbox{otherwise}, \ z.</math>(पृ. 225)
:<math>\mu y_{y<z} R(y). \ \ \mbox{The least} \ y<z \ \mbox{such that} \ R(y), \ \mbox{if} \ (\exists y)_{y<z} R(y); \ \mbox{otherwise}, \ z.</math>(पृ. 225)


[[स्टीफन क्लेन]] का कहना है कि चर y की सीमा पर छह असमानता प्रतिबंधों में से किसी एक की अनुमति है, अर्थात y < z, y ≤ z, w < y < z, w < y ≤ z, w ≤ y < z और w ≤ y ≤ z। जब संकेतित श्रेणी में कोई y नहीं है जैसे कि R(y) [ सत्य है ], तो μy अभिव्यक्ति का मान श्रेणी की बुनियादी संख्या है (पृष्ठ 226); यही कारण है कि उपरोक्त परिभाषा में गलती z दिखाई देता है। जैसा कि नीचे दिखाया गया है, परिबद्ध μ-संचालक μy<sub>''y''<''z''</sub> इसे दो आदिम पुनरावर्ती कार्यों के संदर्भ में परिभाषित किया गया है जिन्हें परिमित योग Σ और परिमित उत्पाद Π कहा जाता है, एक विधेय फलन जो परीक्षण करता है और एक प्रतिनिधित्व फलन जो {t, f} को {0, 1} में परिवर्तित करता है।
[[स्टीफन क्लेन]] का कहना है कि चर y की सीमा पर छह असमानता प्रतिबंधों में से किसी की अनुमति है, अर्थात y < z, y ≤ z, w < y < z, w < y ≤ z, w ≤ y < z और w ≤ y ≤ z। "जब सूचित श्रेणी में R(y) [सत्य होने] वाले कोई y नहीं होता, तो "μy" अभिव्यक्ति की मान्यता सूची की कार्डिनल संख्या होती है" (पृष्ठ 226); यही कारण है कि उपरोक्त परिभाषा में गलती "z" दिखाई देता है। जैसा कि नीचे दिखाया गया है, परिबद्ध μ-संचालक " μy<sub>''y''<''z''</sub> " को दो प्रारंभिक पुनरावृत्ति फलन, अर्थात संलग्न सूम Σ और संलग्न उत्पाद Π, प्रेडिकेट फलन और प्रतिनिदित फलन के रूप में परिभाषित किया जाता है, जो {t, f} को {0, 1} में बदलता है।


अध्याय XI §57 सामान्य पुनरावर्ती कार्यों में, क्लेन निम्नलिखित विधि से चर y पर असीम μ-संचालक को परिभाषित करता है,
अध्याय XI §57 "सामान्य पुनरावर्ती फलन में", क्लीन ने चरण से निर्धारित असीमित μ-संचालक को निम्नलिखित विधि से परिभाषित किया है,
:<math>(\exists y) \mu y R(y) = \{ \mbox{the least (natural number)}\ y \ \mbox{such that} \ R(y)\}</math>(पृ. 279, कहां<math>(\exists y)</math>इसका मतलब है कि कोई ऐसा अस्तित्व है कि... )
:<math>(\exists y) \mu y R(y) = \{ \mbox{the least (natural number)}\ y \ \mbox{such that} \ R(y)\}</math>(पृ. 279, कहां<math>(\exists y)</math> इसका कारण है कि कोई ऐसा अस्तित्व है कि... )


इस उदाहरण में R स्वयं, या इसका प्रतिनिधित्व करने वाला कार्य, संतुष्ट होने पर 0 प्रदान करता है (अर्थात सत्य प्रदान करता है); फलन फिर संख्या y प्रदान करता है। y पर कोई ऊपरी सीमा उपस्थित नहीं है, इसलिए इसकी परिभाषा में कोई असमानता की अभिव्यक्ति दिखाई नहीं देती है।
इस उदाहरण में R स्वयं, या इसका प्रतिनिधित्व करने वाला फलन, जब यह संतोषित होता है (अर्थात सत्य होता है), 0 प्राप्त करता है; तब फलन नंबर y प्राप्त करता है। y पर कोई ऊपरी सीमा उपस्थित नहीं है, इसलिए उसकी परिभाषा में कोई असमेकता अभिव्यक्तियाँ नहीं होती हैं।


किसी दिए गए R(y) के लिए असीम μ-संचालक μyR(y) (नोट (Ey) के लिए कोई आवश्यकता नहीं) एक आंशिक फलन है। इसके अतिरिक्त क्लेन इसे एक संपूर्ण फलन के रूप में बनाता है (cf. पृष्ठ 317):
दिए गए R(y) के लिए असीम μ-संचालक μyR(y) (ध्यान दें कि "(Ey)" की कोई आवश्यकता नहीं है) आंशिक फलन है। क्लीन ने इसे इसके अतिरिक्त पूर्ण फलन के रूप में बदला है (पृ. 317):


<math> \varepsilon yR(x,y) = \begin{cases}
<math> \varepsilon yR(x,y) = \begin{cases}
Line 21: Line 21:
\end{cases}</math>""  
\end{cases}</math>""  


असीम μ-संचालक के कुल संस्करण का अध्ययन उच्च-क्रम रिवर्स गणित में किया जाता है ({{harvtxt|Kohlenbach|2005}}) निम्नलिखित रूप में:
असीम μ-संचालक का पूर्ण संस्करण का अध्ययन उच्च-क्रम रिवर्स गणित में किया जाता है ({{harvtxt|कोहलेंबाच |2005}} निम्नलिखित रूप में:


<math>(\exists \mu^2)(\forall f^1)\big( (\exists n^0)(f(n)=0) \rightarrow f(\mu(f))=0 \big),</math>
<math>(\exists \mu^2)(\forall f^1)\big( (\exists n^0)(f(n)=0) \rightarrow f(\mu(f))=0 \big),</math>


जहां सुपरस्क्रिप्ट का अर्थ है कि n शून्य क्रम है, f प्रथम क्रम है, और μ दूसरे क्रम है। यह सिद्धांत बिग फाइव सिस्टम रिवर्स गणित अंकगणितीय समझ ACA0|ACA को जन्म देता है जब इसे उच्च-क्रम विपरीत गणित के सामान्य आधार सिद्धांत के साथ जोड़ा जाता है।{{citation needed|date=November 2022}}
जहाँ ऊपर संकेत के माध्यम से नीचे की ओर यह अर्थात् n जीरोथ-क्रम, f प्रथम-क्रम है, और μ द्वितीय-क्रम है। यह अक्षमीयता उच्च-क्रम रिवर्स गणित की सामान्य बेस सिद्धांत के साथ मिलाकर बड़े पांच प्रणाली ACA0 की उत्पन्न करता है।  


== गुण ==
== गुण ==


(i) [[आदिम पुनरावर्ती कार्य]] के संदर्भ में, जहां μ-संचालक का खोज चर y घिरा हुआ है, उदाहरण के लिए y < z नीचे दिए गए सूत्र में, यदि विधेय R आदिम पुनरावर्ती है (क्लीन प्रूफ़ #E पृष्ठ 228), तो
(i) [[आदिम पुनरावर्ती कार्य|प्रारंभिक पुनरावर्ती]] फलन के संदर्भ में, जहां μ-संचालक का अविष्कार चर y घिरा हुआ है, उदाहरण के लिए y < z नीचे दिए गए सूत्र में, यदि विधेय R प्रारंभिक पुनरावर्ती है (क्लीन प्रूफ़ E पृष्ठ 228), तो
: μy<sub>''y''<''z''</sub>आर(, एक्स<sub>1</sub>, ..., एक्स<sub>n</sub>) एक आदिम पुनरावर्ती कार्य है।
: μ''y<sub>y</sub>''<sub><''z''</sub>R(''y'', ''x''<sub>1</sub>, ..., ''x''<sub>n</sub>) प्रारंभिक पुनरावृत्ति फलन है।


(ii) कुल पुनरावर्ती फलन के संदर्भ में, जहां खोज चर y असीमित है किन्तु सभी मान x के लिए उपस्थित होने की गारंटी है<sub>''i''</sub> कुल पुनरावर्ती विधेय आर के पैरामीटर,
(ii) कुल पुनरावर्ती फलन के संदर्भ में, जहां अविष्कार चर y असीमित होती है किन्तु सभी मान x<sub>''i''</sub> के लिए उपस्थित होने की गारंटी है कुल पुनरावर्ती विधेय आर के पैरामीटर,
:(एक्स<sub>1</sub>),...,(एक्स<sub>''n''</sub>) (आई) आर(वाई, एक्स<sub>''i''</sub>, ..., एक्स<sub>''n''</sub>) का तात्पर्य है कि μyR(y, x<sub>''i''</sub>, ..., एक्स<sub>''n''</sub>) एक पूर्ण पुनरावर्ती कार्य है।
:(''x''<sub>1</sub>),...,(''x<sub>n</sub>'') (Ey) R(''y'', ''x<sub>i</sub>'', ..., ''x<sub>n</sub>'') का तात्पर्य है कि μ''y''R(''y'', ''x<sub>i</sub>'', ..., ''x<sub>n</sub>'') पूर्ण पुनरावर्ती फलन होता है। यहाँ (x<sub>''i''</sub>) "सभी ''x<sub>i</sub>'' के लिए" का अर्थ है और Ey "कम से कम y का उपस्थित होना" का अर्थ होता है (क्लेन (1952) पृ. 279 का अनुकरण करें।)
:यहाँ (x<sub>''i''</sub>) का मतलब सभी x के लिए है<sub>''i''</sub>और आई का मतलब है कि वाई का कम से कम एक मान उपस्थित है जैसे... (सीएफ क्लेन (1952) पृष्ठ 279।)


फिर पांच आदिम पुनरावर्ती संचालक और असीमित-किन्तु-कुल μ-संचालक उस चीज़ को जन्म देते हैं जिसे क्लेन ने सामान्य पुनरावर्ती फलन कहा है (अर्थात छह रिकर्सन संचालकों द्वारा परिभाषित कुल फलन)।
इसके बाद पांच प्रारंभिक पुनरावर्ती संचालक और असीमित-किन्तु-कुल μ-संचालक "सामान्य" पुनरावृत्ति फलन की उत्पन्न करते हैं (अर्थात छह पुनरावृत्ति संचालक द्वारा परिभाषित पूरे फलन का समूह)।


(iii) [[आंशिक पुनरावर्ती कार्य]] के संदर्भ में: मान लीजिए कि संबंध आर तभी कायम रहता है जब आंशिक पुनरावर्ती फलन शून्य में परिवर्तित हो जाता है। और मान लीजिए कि वह आंशिक पुनरावर्ती फलन जब भी μyR (y, x) अभिसरण करता है (कुछ, जरूरी नहीं कि शून्य)<sub>1</sub>, ..., एक्स<sub>''k''</sub>) परिभाषित है और y μyR(y, x है<sub>1</sub>, ..., एक्स<sub>''k''</sub>) या छोटा. फिर फलन μyR(y, x<sub>1</sub>, ..., एक्स<sub>''k''</sub>) भी एक आंशिक पुनरावर्ती कार्य है।
(iii) [[आंशिक पुनरावर्ती कार्य|आंशिक पुनरावर्ती]] फलन के संदर्भ में: मान लीजिए कि संबंध R तभी सत्य होता है जब आंशिक पुनरावर्ती फलन शून्य में परिवर्तित हो जाता है। और मान लीजिए कि वह आंशिक पुनरावर्ती फलन जब भी μyR (y, x) परिभाषित होता है और y, μ''y''R(''y'', ''x''<sub>1</sub>, ..., ''x<sub>k</sub>'') या उससे छोटा होता है, तो वह किसी चीज़ (शून्य की आवश्यकता नहीं) की ओर आगमन करता है। तब फलन μ''y''R(''y'', ''x''<sub>1</sub>, ..., ''x<sub>k</sub>'') भी आंशिक पुनरावृत्ति फलन होता है।


<!--If for every <math>(y_1,\ldots,y_k)</math> there is some ''x'' such that  <math>R(x,y_1,\ldots,y_k)</math>, then the function <math>\mu x R(x,y_1,\ldots,y_k)</math> is total. If it is a total function and also a partial recursive function then it is a [[total recursive function]].-->
μ-संचालक का उपयोग म्यू-रिकर्सिव फलन μ रिकर्सिव फलन के रूप में गणना योग्य फलन के लक्षण वर्णन में किया जाता है।
μ-संचालक का उपयोग म्यू-रिकर्सिव फलन|μ रिकर्सिव फलन के रूप में गणना योग्य कार्यों के लक्षण वर्णन में किया जाता है।


[[रचनात्मक गणित]] में, असीम सर्च संचालक मार्कोव के सिद्धांत से संबंधित है।
[[रचनात्मक गणित]] में, असीम सर्च संचालक मार्कोव के सिद्धांत से संबंधित होता है।


== उदाहरण ==
== उदाहरण ==


=== उदाहरण 1: परिबद्ध μ-संचालक एक आदिम पुनरावर्ती फलन है ===
=== उदाहरण 1: परिबद्ध μ-संचालक प्रारंभिक पुनरावर्ती फलन है ===


:निम्नलिखित में 'x' स्ट्रिंग x को दर्शाता है<sub>''i''</sub>, ..., एक्स<sub>''n''</sub>.
:निम्नलिखित में 'x' स्ट्रिंग ''x<sub>i</sub>'', ..., ''x<sub>n</sub>'' को प्रस्तुत करता है।


बंधे हुए μ-संचालक को दो आदिम पुनरावर्ती कार्यों (इसके बाद पीआरएफ) के संदर्भ में व्यक्त किया जा सकता है, जिनका उपयोग स्थिति फलन को परिभाषित करने के लिए भी किया जाता है - उत्पाद-शब्दों का Π और योग-योग Σ (सीएफ क्लेन #) बी पेज 224). (आवश्यकतानुसार, चर के लिए कोई भी सीमा जैसे s ≤ t या t < z, या 5 < x < 17 आदि उपयुक्त है)। उदाहरण के लिए:
बंधे हुए μ-संचालक को दो प्रारंभिक पुनरावर्ती फलन (इसके बाद "पीआरएफ") के संदर्भ में व्यक्त किया जा सकता है, जिनका उपयोग स्थिति फलन को परिभाषित करने के लिए भी किया जाता है - उत्पाद-शब्दों का Π और योग-योग Σ (सीएफ क्लेन B पृष्ठ 224 की तुलना करें)(जैसे-जैसे आवश्यकता होती है, कोई भी चरण जैसे s ≤ t या t < z, या 5 < x < 17 आदि चुन सकते हैं)। उदाहरण के लिए:
:*Π<sub>''s''≤''t''</sub> f<sub>''s''</sub>(एक्स, ''एस'') = एफ<sub>0</sub>(एक्स, 0) × एफ<sub>1</sub>(एक्स, 1) × ... × एफ<sub>t</sub>(एक्स, ''टी'')
:*Π<sub>''s''≤''t''</sub> f<sub>''s''</sub>('''x''', ''s'') = f<sub>0</sub>('''x''', 0) × f<sub>1</sub>('''x''', 1) × ... × f<sub>t</sub>('''x''', ''t'')
:*एस<sub>''t''<''z''</sub> g<sub>''t''</sub>(एक्स, ''टी'') = जी<sub>0</sub>(एक्स, 0) + जी<sub>1</sub>(एक्स, 1) + ... + जी<sub>z-1</sub>(एक्स, ''जेड''-1)
:*Σ<sub>''t''<''z''</sub> g<sub>''t''</sub>('''x''', ''t'') = g<sub>0</sub>('''x''', 0) + g<sub>1</sub>('''x''', 1) + ... + g<sub>z-1</sub>('''x''', ''z''-1)


आगे बढ़ने से पहले हमें एक फलन ψ पेश करने की आवश्यकता है जिसे विधेय आर का प्रतिनिधित्व करने वाला फलन कहा जाता है। फलन ψ को इनपुट (t = सत्य, f = मिथ्या) से आउटपुट (0, 1) (''ऑर्डर नोट करें!'') से परिभाषित किया गया है। इस स्थितियों में ψ का इनपुट। अर्थात {टी, एफ}R के आउटपुट से आ रहा है:
आगे बढ़ने से पहले हमें फलन ψ को "प्रतिनिदित करने वाला फलन" के रूप में परिचय देने की आवश्यकता है, जो प्रमेय R का है। फलन ψ को इनपुट (t = "सत्यता", f = "असत्यता") से आउटपुट (0, 1) तक परिभाषित किया जाता है (ध्यान दें अनुक्रम!)इस स्थितियों में ψ के इनपुट, अर्थात {t, f}, प्रमेय R के आउटपुट से आ रहे हैं:
:* ψ(आर = टी) = 0
:* ψ(R = t) = 0
:* ψ(आर = एफ) = 1
:* ψ(R = f) = 1


क्लेन दर्शाता है कि μ''y''<sub>''y''<''z''</sub>R(y) को इस प्रकार परिभाषित किया गया है; हम देखते हैं कि उत्पाद फलन Π एक बूलियन या संचालक की तरह कार्य कर रहा है, और योग Σ कुछ सीमा तक बूलियन और की तरह कार्य कर रहा है, किन्तु केवल {1, 0} के अतिरिक्त {Σ≠0, Σ=0} उत्पन्न कर रहा है:
क्लेन दर्शाता है कि μ''y''<sub>''y''<''z''</sub>R(y) निम्नलिखित रूप में परिभाषित होता है; हम देखते हैं कि उत्पाद फलन Π बूलियन OR संचालक की प्रकार काम कर रहा है, और योग फलन Σ किसी प्रकार बूलियन AND की प्रकार काम कर रहा है, किन्तु केवल {Σ≠0, Σ=0} नहीं किंतु {1, 0} नहीं पैदा कर रहा है:
: μy<sub>''y''<''z''</sub>आर(वाई) = एस<sub>''t''<''z''</sub>Π<sub>''s''≤''t''</sub> ψ(R(x, ''t'', ''s'')) =
: μ''y<sub>y</sub>''<sub><''z''</sub>R(''y'') = Σ<sub>''t''<''z''</sub>Π<sub>''s''≤''t''</sub> ψ(R('''x''', ''t'', ''s'')) =
: [ψ(x, 0, 0)] +
: [ψ(x, 0, 0)] +
: [ψ(x, 1, 0) × ψ(x, 1, 1)] +
: [ψ(x, 1, 0) × ψ(x, 1, 1)] +
Line 67: Line 65:
: [ψ(x, ''z''-1, 0) × ψ(x, ''z''-1, 1) × ψ(x, ''z''-1, 2) × . . . . . . . . × ψ(x, ''z''-1, ''z''-1)]
: [ψ(x, ''z''-1, 0) × ψ(x, ''z''-1, 1) × ψ(x, ''z''-1, 2) × . . . . . . . . × ψ(x, ''z''-1, ''z''-1)]


:ध्यान दें कि ''Σ वास्तव में आधार के साथ एक आदिम पुनरावृत्ति है'' Σ(x, 0) = 0 ''और प्रेरण चरण'' Σ(x, ''y''+1) = Σ(x, ' y'') + Π( x, ''y''). उत्पाद Π आधार चरण Π(x, 0) = ψ(x, 0) और प्रेरण चरण Π(x, y''+1) = Π( x, ''y'') × के साथ एक आदिम पुनरावर्तन भी है ψ(x, ''y''+1)'
:''ध्यान दें कि Σ वास्तव में प्रारंभिक पुनरावृत्ति है जिसमें आधार Σ(x, 0) = 0 है और इंडक्शन स्टेप Σ(x, y+1) = Σ(x, y) + Π( x, y) है। उत्पाद Π भी प्रारंभिक पुनरावृत्ति है जिसमें आधार कदम Π(x, 0) = ψ(x, 0) होता है और इंडक्शन स्टेप Π(x, y+1) = Π(x, y) × ψ(x, y+1) होता है।''


यदि क्लेन द्वारा दिए गए उदाहरण के साथ देखा जाए तो समीकरण आसान है। उन्होंने अभी प्रतिनिधित्व फलन ψ(R(''y'')) के लिए प्रविष्टियां बनाईं। उन्होंने ψ(x, ''y'' के अतिरिक्त प्रतिनिधित्व करने वाले कार्यों को χ(''y'') निर्दिष्ट किया:
इस समीकरण को उदाहरण के साथ समझना आसान होता है, जैसा कि क्लीन द्वारा दिया गया है। उन्होंने प्रतिनिदित करने वाले फलन ψ(R(y)) के लिए एंट्रीज केवल तैयार की थीं। उन्होंने प्रतिनिदित करने वाले फलन के लिए χ(y) को ψ(x, y) के अतिरिक्त चिन्हित किया था।
{| class="wikitable" style="text-align: center; vertical-align: bottom;"
{| class="wikitable" style="text-align: center; vertical-align: bottom;"
|-
|-
Line 124: Line 122:




=== उदाहरण 2: असीम μ-संचालक आदिम-पुनरावर्ती नहीं है ===
=== उदाहरण 2: असीम μ-संचालक आदिम-पुनरावर्ती नहीं होता है ===
असीम μ-संचालक-फलन μy-वह है जिसे सामान्यतः ग्रंथों में परिभाषित किया गया है। किन्तु पाठक को आश्चर्य हो सकता है कि असंबद्ध μ-संचालक किसी अन्य प्राकृतिक संख्या के अतिरिक्त शून्य उत्पन्न करने के लिए फलन R('x', y) की खोज क्यों कर रहा है।
असीम μ-संचालक-फलन μy-वह है जिसे सामान्यतः ग्रंथों में परिभाषित किया गया है। किन्तु पाठक को आश्चर्य हो सकता है कि असंबद्ध μ-संचालक किसी अन्य प्राकृतिक संख्या के अतिरिक्त शून्य उत्पन्न करने के लिए फलन R('x', y) की अविष्कार क्यों कर रहा है।
:फुटनोट में मिन्स्की अपने संचालक को तब समाप्त करने की अनुमति देता है जब अंदर का फलन पैरामीटर k से मेल खाता है; यह उदाहरण इसलिए भी उपयोगी है क्योंकि यह किसी अन्य लेखक का प्रारूप दिखाता है:
:फुटनोट में मिन्स्की अपने संचालक को तब समाप्त करने की अनुमति देता है जब अंदर का फलन पैरामीटर k से मेल खाता है; यह उदाहरण इसलिए भी उपयोगी है क्योंकि यह किसी अन्य लेखक का प्रारूप दिखाता है:
:: μ के लिए<sub>''t''</sub>[φ(t) = k] (पृ. 210)
:: "μt[φ(t) = k]" (पृ. 210)


शून्य का कारण यह है कि असीम संचालक μy को फलन उत्पाद Π के संदर्भ में परिभाषित किया जाएगा, इसके सूचकांक y को μ-संचालक खोज के रूप में बढ़ने की अनुमति दी जाएगी। जैसा कि ऊपर दिए गए उदाहरण में बताया गया है, उत्पाद Π<sub>''x''<''y''</sub> संख्याओं ψ(x, 0) *, ..., * ψ(x, ''y'') की एक स्ट्रिंग में शून्य प्राप्त होता है जब भी इसके सदस्यों में से एक ψ(x, ''i'') शून्य होता है:
शून्य का कारण यह है कि असीम संचालक μy को फलन "उत्पाद" Π के संदर्भ में परिभाषित किया जाएगा, जिसमें निर्देशिका y को "बढ़ने" की अनुमति होती है जैसे-जैसे μ-संचालक अविष्कार करता है। जैसा कि ऊपर के उदाहरण में दिखाया गया है, स्ट्रिंग संख्याओं ψ('''x''', 0) *, ..., * ψ('''x''', ''y'') का उत्पाद Π<sub>''x''<''y''</sub> कभी भी जब भी ψ('''x''', ''i'') में से कोई भी सदस्य शून्य होता है, तो वह 0 प्राप्त करता है:
:Π<sub>''s''<''y''</sub> = ψ(x, 0) * , ..., * ψ(x, ''y'') = 0
:Π<sub>''s''<''y''</sub> = ψ(x, 0) * , ..., * ψ(x, ''y'') = 0


यदि कोई ψ(x, ''i'') = 0 जहां 0≤''i''≤''s'' है। इस प्रकार Π एक बूलियन और की तरह कार्य कर रहा है।
यदि कोई ψ(x, ''i'') = 0 जहां 0≤''i''≤''s'' है। इस प्रकार Π बूलियन AND की प्रकार फलन कर रहा है।


फलन μ''y'' आउटपुट के रूप में एक एकल प्राकृतिक संख्या ''y'' = {0, 1, 2, 3, ...} उत्पन्न करता है। चूँकि, संचालक के अंदर कुछ स्थितियों में से एक दिखाई दे सकती है: () एक संख्या-सैद्धांतिक फलन χ जो एक प्राकृतिक संख्या उत्पन्न करता है, या (बी) एक विधेय आर जो या तो {t = true, f = false} उत्पन्न करता है। (और, ''आंशिक'' पुनरावर्ती कार्यों के संदर्भ में क्लेन ने बाद में एक तीसरा परिणाम स्वीकार μ = अनिर्णीत।<ref>pp.&nbsp;332ff</ref>) किया गया है।
फलन μ''y'' "उत्पाद" के रूप में एकल प्राकृतिक संख्या ''y'' = {0, 1, 2, 3, ...} उत्पन्न करता है। चूँकि, संचालक के अंदर कुछ स्थितियों में से दिखाई दे सकती है: (a) "संख्या-सैद्धांतिक फलन" χ जो प्राकृतिक संख्या उत्पन्न करता है, या (b)"प्रतिलोम" R जो या {t = सत्य, f = असत्य} प्राप्त करता है। (और, ''आंशिक'' पुनरावर्ती फलन के संदर्भ में क्लेन ने बाद में तीसरा परिणाम की अनुमति देते हैं μ = निर्धारित")।<ref>pp.&nbsp;332ff</ref> किया गया है।


क्लेन ने दो स्थितियों () और (बी) को संभालने के लिए असीम μ-संचालक की अपनी परिभाषा को विभाजित किया है। स्थिति (बी) के लिए, इससे पहले कि विधेय R(x, ''y'') उत्पाद Π में अंकगणितीय क्षमता में काम कर सके, इसके आउटपुट {t, f} को पहले इसके ''प्रतिनिधित्व फलन χ'' द्वारा संचालित किया जाना चाहिए। ' {0, 1} उत्पन्न करने के लिए। और स्थिति () के लिए यदि एक परिभाषा का उपयोग किया जाना है तो ''संख्या सैद्धांतिक फलन χ'' को μ-संचालक को संतुष्ट करने के लिए शून्य उत्पन्न करना होगा। इस स्थितियों के सुलझने के साथ, वह एकल प्रमाण III के साथ प्रदर्शित करता है कि या तो प्रकार () या (बी) पांच आदिम पुनरावर्ती संचालकों के साथ मिलकर (कुल) कुल पुनरावर्ती कार्य उत्पन्न करते हैं, कुल कार्य के लिए इस प्रावधान के साथ किया गया है।
क्लीन अपने असीमित μ-संचालक की परिभाषा को दो स्थितियों (a) और (b) को नियंत्रण करने के लिए विभाजित करते हैं। स्थिति (b) के लिए, पूर्व प्रतिनिदित फलन R(x, y) को उसके प्रतिनिदित फलन χ द्वारा पहले {t, f} से "ऑपरेट किया जाना" चाहिए, ताकि {0, 1} प्राप्त हो। और स्थिति (a) के लिए यदि परिभाषा का उपयोग किया जाना है तो संख्यात्मक फलन χ को शून्य प्राप्त करने के लिए "संतुष्ट" करना आवश्यक है। इस स्थितियों में, उन्होंने एकल "प्रूफ III" के साथ दिखाया है कि प्रकार (a) या (b) और पांच प्रारंभिक पुनरावृत्ति संचालक द्वारा जनित होने वाले (कुल) पुनरावृत्ति फलन को देते हैं, इस उल्लेख के साथ कि पूर्ण फलन के लिए:
: ''सभी मापदंडों के लिए'' x, ''यह दिखाने के लिए एक प्रदर्शन प्रदान किया जाना चाहिए कि एक ''y'' उपस्थित है जो संतुष्ट करता है (ए)'' μ''y''ψ(x, ''y'') ''या (बी)'' μ''y''R(x, ''y''),
: ''सभी मापदंडों के लिए'' x, ''यह दिखाने के लिए प्रदर्शन प्रदान किया जाना चाहिए कि ''y'' उपस्थित है जो संतुष्ट करता है (ए)'' μ''y''ψ(x, ''y'') ''या (बी)'' μ''y''R(x, ''y''),
क्लेन एक तीसरी स्थिति (सी) को भी स्वीकार करता है जिसके लिए सभी x के प्रदर्शन की आवश्यकता नहीं है, एक ''y'' उपस्थित है जैसे कि ψ(x, ''y'')। वह अपने प्रमाण में इसका उपयोग करता है कि गिनाए जा सकने वाले कार्यों से अधिक कुल पुनरावर्ती कार्य उपस्थित हैं''; सी.एफ. फ़ुटनोट #संपूर्ण कार्य प्रदर्शन किया जाता है ।''
क्लेन तीसरी स्थिति (सी) को भी स्वीकार करता है जिसके लिए सभी x के प्रदर्शन की आवश्यकता नहीं है, ''y'' उपस्थित है जैसे कि ψ(x, ''y'')। वह अपने प्रमाण में इसका उपयोग करता है कि गिनाए जा सकने वाले फलन से अधिक कुल पुनरावर्ती फलन उपस्थित हैं''; सी.एफ. फ़ुटनोट संपूर्ण फलन प्रदर्शन किया जाता है ।''


क्लेन का प्रमाण अनौपचारिक है और पहले उदाहरण के समान एक उदाहरण का उपयोग करता है, किन्तु पहले वह μ-संचालक को एक अलग रूप में डालता है जो फलन χ पर काम करने वाले उत्पाद-शब्द Π का उपयोग करता है जो एक प्राकृतिक संख्या ''n'' उत्पन्न करता है, जो कोई भी प्राकृतिक संख्या हो सकती है, और उस स्थिति में 0 जब यू-संचालक का परीक्षण संतुष्ट हो जाता है।
क्लेन का प्रमाण अनौपचारिक है और पहले उदाहरण के समान उदाहरण का उपयोग करता है, किन्तु पहले वह μ-संचालक को अलग रूप में डालता है जो फलन χ पर काम करने वाले उत्पाद-शब्द Π का उपयोग करता है जो प्राकृतिक संख्या ''n'' उत्पन्न करता है, जो कोई भी प्राकृतिक संख्या हो सकती है, और उस स्थिति में 0 जब यू-संचालक का परीक्षण संतुष्ट हो जाता है।


: परिभाषा Π-फलन के साथ पुनर्गठित होती है:
: परिभाषा Π-फलन के साथ पुनर्गठित होती है,
:μ''y''<sub>''y''<''z''</sub>एक्स(वाई) =
:μ''y<sub>y</sub>''<sub><''z''</sub>χ(''y'') ==
:*(i): π('x', y) = π<sub>''s''<''y''</sub>χ(x, ''s'')
:*(i): π('x', y) = π<sub>''s''<''y''</sub>χ(x, ''s'')
:*(ii): φ(x) = τ(π(x, ''y''), π(x, ''y' ''), ''y'')
:*(ii): φ(x) = τ(π(x, ''y''), π(x, ''y' ''), ''y'')
:*(iii): τ(''z' '', 0, ''y'') = ''y'' ;τ(''u'', ''v'', ''w'') ''u'' = 0 या ''v'' > 0 के लिए अपरिभाषित है।
:*(iii): τ(''z' '', 0, ''y'') = ''y'' ;τ(''u'', ''v'', ''w'') ''u'' = 0 या ''v'' > 0 के लिए अपरिभाषित है।


यह सूक्ष्म है. पहली नज़र में समीकरण आदिम पुनरावर्तन का उपयोग करते हुए प्रतीत होते हैं। किन्तु क्लेन ने हमें सामान्य रूप का आधार चरण और प्रेरण चरण प्रदान नहीं किया है:
यह सूक्ष्म है। पहली देखरेख में समीकरण प्रारंभिक पुनरावर्तन का उपयोग करते हुए प्रतीत होते हैं। किन्तु क्लेन ने हमें सामान्य रूप का आधार चरण और प्रेरण चरण प्रदान नहीं किया है,
:* आधार चरण: φ(0, x) = φ(x)
:* आधार चरण: φ(0, x) = φ(x)
:* प्रेरण चरण: φ(0, x) = ψ(y, φ(0,x), x)
:* प्रेरण चरण: φ(0, x) = ψ(y, φ(0,x), x)


यह देखने के लिए कि क्या हो रहा है, हमें सबसे पहले खुद को याद दिलाना होगा कि हमने प्रत्येक चर ''x'' के लिए एक पैरामीटर (एक प्राकृतिक संख्या) निर्दिष्ट किया है।<sub>''i''</sub>. दूसरा, हम एक उत्तराधिकारी-संचालक को काम पर y (अर्थात y' ) दोहराते हुए देखते हैं। और तीसरा, हम देखते हैं कि फलन μy <sub>''y''<''z''</sub>χ(y, 'x') केवल χ(y,'x') अर्थात χ(0,'x'), χ(1,'x'), ... के उदाहरण उत्पन्न कर रहा है जब तक कि एक उदाहरण 0 प्राप्त न हो जाए। चौथा , जब एक उदाहरण χ(n, 'x') से 0 प्राप्त होता है तो यह τ के मध्य पद का कारण बनता है, अर्थात v = π('x', y' ) से 0 प्राप्त होता है। अंत में, जब मध्य पद v = 0, μy होता है<sub>''y''<''z''</sub>χ(y) लाइन (iii) निष्पादित करता है और बाहर निकलता है। क्लेन की समीकरणों (ii) और (iii) की प्रस्तुति का आदान-प्रदान इस बिंदु को बनाने के लिए किया गया है कि रेखा (iii) एक निकास का प्रतिनिधित्व करती है - एक निकास केवल तभी लिया जाता है जब खोज सफलतापूर्वक χ(y) और मध्य उत्पाद-शब्द π को संतुष्ट करने के लिए एक y पाती है। ('x', y' ) 0 है; इसके बाद संचालक अपनी खोज को τ(z', 0, y) = y के साथ समाप्त करता है।
यह देखने के लिए कि क्या हो रहा है, हमें सबसे पहले स्वयं को याद दिलाना होगा कि हमने प्रत्येक चर ''x'' के लिए पैरामीटर ( प्राकृतिक संख्या) निर्दिष्ट किया है। दूसरा, हम उत्तराधिकारी-संचालक को काम पर y (अर्थात y' ) दोहराते हुए देखते हैं। और तीसरा, हम देखते हैं कि फलन μ''y'' <sub>''y''<''z''</sub>χ(''y'', '''x'<nowiki/>'')''''' ''केवल χ(''y'',x) अर्थात χ(0,x), χ(1,x), ... के उदाहरण उत्पन्न कर रहा है जब तक कि उदाहरण 0 प्राप्त न हो जाए। चौथा , जब उदाहरण χ(''n'', x) से 0 प्राप्त होता है तो यह τ के मध्य पद का कारण बनता है, अर्थात v = π(x, ''y ) से 0 प्राप्त होता है। अंत में, जब मध्य पद ''v'' = 0, μ''y<sub>y</sub>''<sub><''z''</sub>χ(''y'') होता है, लाइन (iii) निष्पादित करता है और बाहर निकलता है। क्लेन की समीकरणों (ii) और (iii) की प्रस्तुति का आदान-प्रदान इस बिंदु को बनाने के लिए किया गया है कि रेखा (iii) निकास का प्रतिनिधित्व करती है - निकास केवल तभी लिया जाता है जब अविष्कार सफलतापूर्वक χ(y) और मध्य उत्पाद-शब्द π को संतुष्ट करने के लिए y पाती है। ('x', y' ) 0 है; इसके बाद संचालक अपनी अविष्कार को τ(z', 0, y) = y के साथ समाप्त करता है।
: τ(π('x', y), π('x', y' ), y), अर्थात:
: τ(π('x', y), π('x', y' ), y), अर्थात:
:* τ(π('x', 0), π('x', 1), 0),
:* τ(π('x', 0), π('x', 1), 0),
Line 158: Line 156:
:* τ(π('x', 2), π('x', 3), 2)
:* τ(π('x', 2), π('x', 3), 2)
:* τ(π('x', 3), π('x', 4), 3)
:* τ(π('x', 3), π('x', 4), 3)
:* ... जब तक कोई मिलान y=n पर न हो जाए और तब:
:* ... जब तक कोई मिलान y=n पर न हो जाए और तब,
:* τ(z' , 0, y) = τ(z' , 0, n) = n और μ-संचालक की खोज पूरी हो गई है।
:* τ(z' , 0, y) = τ(z' , 0, n) = n और μ-संचालक की अविष्कार पूरी हो गई है।


उदाहरण के लिए क्लेन ... (x) के किसी भी निश्चित मान पर विचार करें<sub>''i''</sub>, ..., एक्स<sub>''n''</sub>) और 'χ(x) के लिए बस 'χ(y)' लिखें<sub>''i''</sub>, ..., एक्स<sub>''n''</sub>), और)' :
उदाहरण के लिए क्लेन (''x<sub>i</sub>'', ..., ''x<sub>n</sub>'') के किसी भी निश्चित मान पर विचार करें और 'χ(x) के लिए बस 'χ(''x<sub>i</sub>'', ..., ''x<sub>n</sub>''), ''y'')'":
{| class="wikitable" style="text-align: center; vertical-align: bottom;"
{| class="wikitable" style="text-align: center; vertical-align: bottom;"
|-
|-
Line 219: Line 217:
|  
|  
|}
|}
<!--


=== उदाहरण 3: एक अमूर्त मशीन के संदर्भ में असीमित μ-ऑपरेटर की परिभाषा ===
[[Category:Machine Translated Page]]
 
दोनों मिन्स्की (1967) पृ. 21 और बूलोस-बर्गेस-जेफरी (2002) पी. 60-61 एक अमूर्त मशीन के रूप में μ-ऑपरेटर की परिभाषा प्रदान करते हैं; फुटनोट देखें #मिन्स्की .281967.29 और बूलोस-बर्गेस-जेफरी .282002.29| से अनबाउंडेड .CE.BC ऑपरेटर के वैकल्पिक अमूर्त मशीन मॉडल|μ की वैकल्पिक परिभाषाएँ।
 
निम्नलिखित प्रदर्शन फ़ुटनोट में उल्लिखित विशिष्टता के बिना मिन्स्की का अनुसरण करता है। प्रदर्शन [[पीनो एक्सिओम्स]] और आदिम पुनरावर्ती कार्यों से निकटता से संबंधित एक उत्तराधिकारी [[काउंटर मशीन]] मॉडल का उपयोग करेगा। मॉडल में (i) निर्देशों की एक तालिका और एक तथाकथित 'राज्य रजिस्टर' के साथ एक सीमित राज्य मशीन शामिल है जिसे हम निर्देश रजिस्टर (आईआर) का नाम देंगे, (ii) कुछ रजिस्टर जिनमें से प्रत्येक में केवल एक ही शामिल हो सकता है प्राकृतिक संख्या, और (iii) निम्नलिखित तालिका में वर्णित चार आदेशों का एक निर्देश सेट:
 
:निम्नलिखित में, प्रतीकवाद [ r ] का अर्थ है , और →r रजिस्टर r के संबंध में एक कार्रवाई को इंगित करता है।
 
{|class="wikitable"
|-
! Instruction
! Mnemonic
! Action on register(s) "r"
! Action on Instruction Register, IR
|-
| CLeaR register
|style="text-align:left;"| CLR ( r )
|style="text-align:left;"| 0 → r
|style="text-align:left;"| [ IR ] + 1 → IR
|-
| INCrement register
| INC ( r )
|style="text-align:left;"| [ r ] + 1 → r
|style="text-align:left;"| [ IR ] + 1 → IR
|-
| Jump if Equal
| JE (r<sub>1</sub>, r<sub>2</sub>, z)
|style="text-align:left;"| none
|style="text-align:left;"| IF [ r<sub>1</sub> ] = [ r<sub>2</sub> ]<br />THEN z → IR <br />ELSE [ IR ] + 1 → IR
|-
| Halt
| H
|style="text-align:left;"| none
|style="text-align:left;"| [ IR ]  → IR
|}
न्यूनतमकरण ऑपरेटर μy[φ('x', y)] के लिए एल्गोरिदम, संक्षेप में, पैरामीटर y (एक प्राकृतिक संख्या) का मान बढ़ने पर फ़ंक्शन φ('x', y) के उदाहरणों का एक अनुक्रम बनाएगा; प्रक्रिया तब तक जारी रहेगी (नीचे नोट † देखें) जब तक फ़ंक्शन φ('x', y) के आउटपुट और कुछ पूर्व-स्थापित संख्या (आमतौर पर 0) के बीच मिलान नहीं हो जाता। इस प्रकार φ('x', y) के मूल्यांकन के लिए, शुरुआत में, इसके प्रत्येक चर 'x' के लिए एक प्राकृतिक संख्या निर्दिष्ट करने और एक रजिस्टर w के लिए एक मिलान संख्या (आमतौर पर 0) और y पंजीकृत करने के लिए एक संख्या (आमतौर पर 0) निर्दिष्ट करने की आवश्यकता होती है।
 
:नोट †: अनबाउंड μ-ऑपरेटर इस प्रयास-से-मिलान प्रक्रिया को अनंत काल तक या जब तक कोई मिलान नहीं हो जाता तब तक जारी रखेगा। इस प्रकार y रजिस्टर असीमित होना चाहिए - यह कई मनमाने आकार धारण करने में सक्षम होना चाहिए। वास्तविक कंप्यूटर मॉडल के विपरीत, अमूर्त मशीन मॉडल इसकी अनुमति देते हैं। एक बाउंडेड μ-ऑपरेटर के मामले में, एक निचला-बाउंड μ-ऑपरेटर y की सामग्री को शून्य के अलावा किसी अन्य संख्या पर सेट करके शुरू करेगा। एक ऊपरी सीमा वाले μ-ऑपरेटर को एक अतिरिक्त रजिस्टर यूबी की आवश्यकता होगी जिसमें वह संख्या शामिल हो जो ऊपरी सीमा के साथ-साथ एक अतिरिक्त तुलना ऑपरेशन का प्रतिनिधित्व करती हो; एक एल्गोरिदम निचली और ऊपरी दोनों सीमाएं प्रदान कर सकता है।
 
निम्नलिखित में हम मान रहे हैं कि निर्देश रजिस्टर (आईआर) निर्देश संख्या n पर μy रूटीन का सामना करता है। इसका पहला कार्य एक समर्पित डब्ल्यू रजिस्टर में एक संख्या स्थापित करना होगा - उस संख्या का एक उदाहरण जो फ़ंक्शन φ('x', y) को एल्गोरिदम समाप्त होने से पहले उत्पन्न करना होगा (शास्त्रीय रूप से यह संख्या शून्य है, लेकिन शून्य के अलावा अन्य संख्याओं के उपयोग के बारे में फ़ुटनोट देखें)। निर्देश n+1 पर एल्गोरिदम की अगली कार्रवाई y रजिस्टर को साफ़ करना होगा - y एक अप-काउंटर के रूप में कार्य करेगा जो 0 से शुरू होता है। फिर निर्देश n+2 पर एल्गोरिदम अपने फ़ंक्शन φ('x', y) का मूल्यांकन करता है - हम मानते हैं कि इसे पूरा करने के लिए j निर्देशों की आवश्यकता होती है - और इसके मूल्यांकन के अंत में φ('x', y) अपना आउटपुट रजिस्टर φ में जमा करता है। (n+j+3) तीसरे निर्देश पर एल्गोरिदम w रजिस्टर में संख्या (जैसे 0) की तुलना φ रजिस्टर में संख्या से करता है - यदि वे समान हैं तो एल्गोरिदम सफल हो गया है और यह निकास के माध्यम से बच जाता है; अन्यथा यह y रजिस्टर की सामग्री को बढ़ाता है और फ़ंक्शन φ('x', y) का फिर से परीक्षण करने के लिए इस नए y-मान के साथ लूप करता है।
 
{| class="wikitable" style="vertical-align: bottom;"
|-
! IR
!
! Instruction
! Action on register
! Action on Instruction Register IR
|-
| ''n''
| μ''y''[φ('''x''', ''y'')]:
| CLR ( w )
|style="text-align:left;"| 0 → ''w''
| [ IR ] + 1 → IR
|-
| ''n''+1
|
| CLR ( ''y'' )
|style="text-align:left;"| 0 → ''y''
| [ IR ] + 1 → IR
|-
| ''n''+2
| ''loop:''
| φ('''x''', ''y'')
|style="text-align:left;"| φ(['''x'''], [''y'']) → φ
| [ IR ] + j + 1 → IR
|-
| ''n''+''j''+3
|
| JE (φ, ''w'', exit)
|style="text-align:left;"| none
| CASE: { IF [ φ ]=[ ''w'' ]<br />THEN ''exit'' → IR <br />ELSE [IR] + 1 → IR }
|-
| ''n''+''j''+4
|
| INC ( ''y'' )
|style="text-align:left;"| [ ''y'' ] + 1 → ''y''
| [ IR ] + 1 → IR
|-
| ''n''+''j''+5
|
| JE (0, 0, loop)
|style="text-align:left;"| Unconditional jump
| CASE: { IF [ r<sub>0</sub> ] =[ r<sub>0</sub> ]<br />THEN ''loop'' → IR <br />ELSE ''loop'' → IR }
|-
| ''n''+''j''+6
| ''exit:''
| ''etc.''
|
|
|}
 
 
== यह भी देखें ==
*[[मैक्कार्थी औपचारिकता]]
 
== फ़ुटनोट ==
 
=== कुल फ़ंक्शन प्रदर्शन ===
 
यदि फ़ंक्शन को कुल फ़ंक्शन होना है तो किसी अन्य विधि (जैसे [[गणितीय प्रेरण]]) द्वारा एक प्रदर्शन अनिवार्य है जो कि इसके पैरामीटर x के मानों के प्रत्येक संयोजन के लिए है<sub>''i''</sub> कुछ प्राकृतिक संख्या y μ-ऑपरेटर को संतुष्ट करेगी ताकि गणना का प्रतिनिधित्व करने वाला एल्गोरिदम समाप्त हो सके:
: ...हमें यह मानने में हमेशा संकोच होना चाहिए कि समीकरणों की एक प्रणाली वास्तव में एक सामान्य-पुनरावर्ती (यानी कुल) फ़ंक्शन को परिभाषित करती है। हमें आम तौर पर इसके लिए सहायक साक्ष्य की आवश्यकता होती है, उदा. एक आगमनात्मक प्रमाण के रूप में, प्रत्येक तर्क मान के लिए, गणना एक अद्वितीय मान के साथ समाप्त होती है। (मिन्स्की (1967) पृ.186)
 
: दूसरे शब्दों में, हमें यह दावा नहीं करना चाहिए कि कोई फ़ंक्शन इस आधार पर प्रभावी रूप से गणना योग्य है कि इसे सामान्य (यानी कुल) पुनरावर्ती दिखाया गया है, जब तक कि यह प्रदर्शन प्रभावी न हो कि यह सामान्य पुनरावर्ती है। (क्लीन (1952) पृष्ठ 319)
 
व्यवहार में इसका क्या अर्थ है, इसके उदाहरण के लिए [[म्यू पुनरावर्ती फ़ंक्शन]] के उदाहरण देखें - यहां तक ​​​​कि सरलतम काटे गए घटाव एल्गोरिदम x - y = d भी अपरिभाषित मामलों के लिए, जब x < y, (1) कोई समाप्ति नहीं, (2) कोई संख्या नहीं (यानी प्रारूप में कुछ गड़बड़ है इसलिए उपज को प्राकृतिक संख्या नहीं माना जाता है), या (3) धोखा: सही प्रारूप में गलत संख्याएं प्राप्त हो सकती हैं। उचित घटाव एल्गोरिथ्म के लिए सभी मामलों पर सावधानीपूर्वक ध्यान देने की आवश्यकता होती है
:(x, y) = {(0, 0), (a, 0), (0, b), (a≥b, b), (a=b, b), (a<b, b)}।
 
लेकिन जब एल्गोरिथ्म को उदाहरणों में अपेक्षित आउटपुट उत्पन्न करने के लिए दिखाया गया है {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, तब तक हम एक असहज भावना से बचे रहते हैं जब तक कि हम एक ठोस प्रदर्शन तैयार नहीं कर लेते कि मामले (x, y) = (n, m) सभी अपेक्षित परिणाम देते हैं। क्लेन की बात पर: क्या हमारा प्रदर्शन (यानी एल्गोरिदम जो हमारा प्रदर्शन है) प्रभावी माने जाने के लिए पर्याप्त है?
 
=== मिन्स्की (1967) और बूलोस-बर्गेस-जेफरी (2002) से अनबाउंडेड μ-ऑपरेटर के वैकल्पिक अमूर्त मशीन मॉडल ===
 
अनबाउंडेड μ-ऑपरेटर को मिन्स्की (1967) पी द्वारा परिभाषित किया गया है। 210 लेकिन एक अजीब दोष के साथ: जब इसका विधेय (यदि-तब-और परीक्षण) संतुष्ट होता है, तो ऑपरेटर t=0 उत्पन्न नहीं करेगा; बल्कि इससे t=2 प्राप्त होता है। मिन्स्की के संस्करण में काउंटर t है, और फ़ंक्शन φ(t, 'x') अपना नंबर रजिस्टर φ में जमा करता है। सामान्य μ परिभाषा रजिस्टर में w में 0 होगा, लेकिन मिन्स्की का मानना ​​है कि इसमें कोई भी संख्या k हो सकती है। मिन्स्की का निर्देश सेट निम्नलिखित के बराबर है जहां JNE = यदि समान नहीं है तो z पर जाएं:
:{सीएलआर (आर), आईएनसी (आर), जेएनई (आर)।<sub>''j''</sub>, आर<sub>''k''</sub>, साथ) }
 
{| class="wikitable" style="text-align:left; "
|-
! IR
!
! Instruction
! Action on register
! Action on Instruction Register, IR
|-
| ''n''
| '''μ''y''φ( ''x'' ):'''
|style="text-align:left;"|CLR ( ''w'' )
| 0 → ''w''
| [ IR ] + 1 → IR
|-
| ''n''+ 1
|
|style="text-align:left;"| CLR ( ''t'' )
| 0 → ''t''
| [ IR ] + 1 → IR
|-
| ''n''+2
| ''loop:''
|style="text-align:left;"| φ (''y'', ''x'')
| φ( [ ''t'' ], [ ''x'' ] ) → φ
| [ IR ] + ''j'' + 1 → IR
|-
| ''n''+''j''+3
|
|style="text-align:left;"| INC ( ''t'' )
| [ ''t'' ] + 1 → ''t''
| [ IR ] + 1 → IR
|-
| ''n''+''j''+4
|
|style="text-align:left;"| JNE (φ, ''w'', loop)
| {{CNone|none}}
| CASE: {  IF [φ] ≠ [''w'']<br />THEN "exit" → IR <br /> ELSE [IR] + 1 → IR }
|-
| ''n''+''j''+5
|
|style="text-align:left;"| INC ( ''t'' )
| [ ''t'' ] + 1 → ''t''
| [ IR ] + 1 → IR
|-
| ''n''+''j''+6
| ''exit:''
| ''etc.''
|
|
|}
अनबाउंडेड μ-ऑपरेटर को बूलोस-बर्गेस-जेफरी (2002) पी द्वारा भी परिभाषित किया गया है। निम्नलिखित के समतुल्य अनुदेश सेट वाली काउंटर मशीन के लिए 60-61:
: {सीएलआर (आर), आईएनसी (आर), डीईसी (आर), जेजेड (आर, जेड), एच }
 
इस संस्करण में काउंटर y को r2 कहा जाता है, और फ़ंक्शन f(x, r2) अपना नंबर रजिस्टर r3 में जमा करता है। शायद बूलोस-बर्गेस-जेफरी स्पष्ट आर3 का कारण ''लूप'' में बिना शर्त छलांग की सुविधा प्रदान करना है; यह अक्सर एक समर्पित रजिस्टर 0 के उपयोग से किया जाता है जिसमें 0 होता है:
 
{|class="wikitable" style="text-align:left; vertical-align:bottom;"
|-
! IR
!
! Instruction
! Action on register
! Action on Instruction Register, IR
|-
| ''n''
| '''μ<sub>''r''<sub>2</sub></sub>[f(''x'', ''r''<sub>2</sub>)]:'''
|style="text-align:left;"| CLR ( ''r''<sub>2</sub> )
| 0 → ''r''<sub>2</sub>
| [ IR ] + 1 → IR
|-
|  ''n''+1
| ''loop:''
|style="text-align:left;"| f(''y'', ''x'')
| f( [ ''t'' ], [ ''x'' ] ) → ''r''<sub>3</sub>
| [ IR ] + ''j'' + 1 → IR
|-
| ''n''+2
|
|style="text-align:left;"| JZ ( ''r''<sub>3</sub>, exit )
| {{CNone|none}}
| IF [ ''r''<sub>3</sub> ] = 0<br />THEN exit → IR<br />ELSE [ IR ] + 1 → IR
|-
| ''n''+''j''+3
|
|style="text-align:left;"| CLR ( ''r''<sub>3</sub> )
| 0 → ''r''<sub>3</sub>
| [ IR ] + 1 → IR
|-
| ''n''+''j''+4
|
|style="text-align:left;"| INC ( ''r''<sub>2</sub> )
| [ ''r''<sub>2</sub> ] + 1 → ''r''<sub>2</sub>
| [ IR ] + 1 → IR
|-
| ''n''+''j''+5
|
|style="text-align:left;"| JZ ( ''r''<sub>3</sub>, loop)
|
| CASE: { IF [ ''r''<sub>3</sub> ] = 0<br />THEN loop → IR <br />ELSE [IR] + 1 → IR }
|-
| ''n''+''j''+6
| ''exit:''
| ''etc.''
|
|
|}
 
 
== संदर्भ ==
{{Reflist}}
*{{citation |author-link=Stephen Kleene |first=Stephen |last=Kleene |title=Introduction to Metamathematics |publisher=North-Holland |orig-year=1952 |date=2009 |isbn=9780923891572 |oclc=935015457}}
* {{Citation | last1=Kohlenbach | first1=Ulrich | title=Higher Order Reverse Mathematics, Reverse Mathematics 2001 | url=https://www2.mathematik.tu-darmstadt.de/~kohlenbach/ | publisher=[[Cambridge University Press]] | isbn= 9781316755846 | year=2005 | series=Lecture notes in Logic | doi=10.1017/9781316755846.018 | pages=281–295 }}
*{{citation |author-link=Marvin L. Minsky |first=Marvin L. |last=Minsky |title=Computation: Finite and Infinite Machines |publisher=Prentice-Hall |orig-year=1967 |date=1972 |isbn=9780131654495 |oclc=974146753}}
: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.
*{{citation |author-link=George Boolos |first1=George |last1=Boolos |author2-link=John P. Burgess |first2=John |last2=Burgess |author3-link=Richard Jeffrey |first3=Richard |last3=Jeffrey |chapter=S6.2 Minimization |chapter-url=https://books.google.com/books?id=0LpsXQV2kXAC&pg=PA70 |title=Computability and Logic |publisher=Cambridge University Press |edition=4th |date=2002 |isbn=9780521701464 |pages=70–71 |url=}}
 
{{DEFAULTSORT:Mu-operator}}
 
[[Category:All articles with unsourced statements]]
[[Category:Articles with invalid date parameter in template]]
[[Category:Articles with unsourced statements from November 2022]]
[[Category:Harv and Sfn no-target errors]]

Latest revision as of 09:25, 22 August 2023

रिकर्सन सिद्धांत में, μ-संचालक, न्यूनतम संचालक, या असीम अविष्कार संचालक किसी दिए गए गुण के साथ सबसे कम प्राकृतिक संख्या की अविष्कार करता है। प्रारंभिक पुनरावर्ती फलन में μ-संचालक को जोड़ने से सभी गणना योग्य फलन को परिभाषित करना संभव हो जाता है।

परिभाषा

मान लीजिए कि R(y, x1, ..., xk) प्राकृतिक संख्याओं पर निश्चित (k+1)-एरी संबंध है। μ-संचालक "μy", असंबद्ध या परिबद्ध रूप में, "अंकगणितीय फलन" है जो प्राकृतिक संख्याओं से प्राकृतिक संख्याओं तक की परिभाषा की जाती है। चूँकि, "μy" में प्राकृतिक संख्याओं पर विधेय (गणित) सम्मिलित है, जिसे ऐसी स्थिति के रूप में माना जा सकता है जो विधेय संतुष्ट होने पर सत्य और ऐसा नहीं होने पर गलत का मूल्यांकन करती है।

घिरे μ-संचालक पहले क्लेन (1952) अध्याय IX प्रारंभिक पुनरावर्ती फलन में दिखाई देता है, §45 विधेय, मुख्य कारक प्रतिनिधित्व इस प्रकार है:

(पृ. 225)

स्टीफन क्लेन का कहना है कि चर y की सीमा पर छह असमानता प्रतिबंधों में से किसी की अनुमति है, अर्थात y < z, y ≤ z, w < y < z, w < y ≤ z, w ≤ y < z और w ≤ y ≤ z। "जब सूचित श्रेणी में R(y) [सत्य होने] वाले कोई y नहीं होता, तो "μy" अभिव्यक्ति की मान्यता सूची की कार्डिनल संख्या होती है" (पृष्ठ 226); यही कारण है कि उपरोक्त परिभाषा में गलती "z" दिखाई देता है। जैसा कि नीचे दिखाया गया है, परिबद्ध μ-संचालक " μyy<z " को दो प्रारंभिक पुनरावृत्ति फलन, अर्थात संलग्न सूम Σ और संलग्न उत्पाद Π, प्रेडिकेट फलन और प्रतिनिदित फलन के रूप में परिभाषित किया जाता है, जो {t, f} को {0, 1} में बदलता है।

अध्याय XI §57 "सामान्य पुनरावर्ती फलन में", क्लीन ने चरण से निर्धारित असीमित μ-संचालक को निम्नलिखित विधि से परिभाषित किया है,

(पृ. 279, कहां इसका कारण है कि कोई ऐसा अस्तित्व है कि... )

इस उदाहरण में R स्वयं, या इसका प्रतिनिधित्व करने वाला फलन, जब यह संतोषित होता है (अर्थात सत्य होता है), 0 प्राप्त करता है; तब फलन नंबर y प्राप्त करता है। y पर कोई ऊपरी सीमा उपस्थित नहीं है, इसलिए उसकी परिभाषा में कोई असमेकता अभिव्यक्तियाँ नहीं होती हैं।

दिए गए R(y) के लिए असीम μ-संचालक μyR(y) (ध्यान दें कि "(Ey)" की कोई आवश्यकता नहीं है) आंशिक फलन है। क्लीन ने इसे इसके अतिरिक्त पूर्ण फलन के रूप में बदला है (पृ. 317):

""

असीम μ-संचालक का पूर्ण संस्करण का अध्ययन उच्च-क्रम रिवर्स गणित में किया जाता है (कोहलेंबाच (2005) निम्नलिखित रूप में:

जहाँ ऊपर संकेत के माध्यम से नीचे की ओर यह अर्थात् n जीरोथ-क्रम, f प्रथम-क्रम है, और μ द्वितीय-क्रम है। यह अक्षमीयता उच्च-क्रम रिवर्स गणित की सामान्य बेस सिद्धांत के साथ मिलाकर बड़े पांच प्रणाली ACA0 की उत्पन्न करता है।

गुण

(i) प्रारंभिक पुनरावर्ती फलन के संदर्भ में, जहां μ-संचालक का अविष्कार चर y घिरा हुआ है, उदाहरण के लिए y < z नीचे दिए गए सूत्र में, यदि विधेय R प्रारंभिक पुनरावर्ती है (क्लीन प्रूफ़ E पृष्ठ 228), तो

μyy<zR(y, x1, ..., xn) प्रारंभिक पुनरावृत्ति फलन है।

(ii) कुल पुनरावर्ती फलन के संदर्भ में, जहां अविष्कार चर y असीमित होती है किन्तु सभी मान xi के लिए उपस्थित होने की गारंटी है कुल पुनरावर्ती विधेय आर के पैरामीटर,

(x1),...,(xn) (Ey) R(y, xi, ..., xn) का तात्पर्य है कि μyR(y, xi, ..., xn) पूर्ण पुनरावर्ती फलन होता है। यहाँ (xi) "सभी xi के लिए" का अर्थ है और Ey "कम से कम y का उपस्थित होना" का अर्थ होता है (क्लेन (1952) पृ. 279 का अनुकरण करें।)

इसके बाद पांच प्रारंभिक पुनरावर्ती संचालक और असीमित-किन्तु-कुल μ-संचालक "सामान्य" पुनरावृत्ति फलन की उत्पन्न करते हैं (अर्थात छह पुनरावृत्ति संचालक द्वारा परिभाषित पूरे फलन का समूह)।

(iii) आंशिक पुनरावर्ती फलन के संदर्भ में: मान लीजिए कि संबंध R तभी सत्य होता है जब आंशिक पुनरावर्ती फलन शून्य में परिवर्तित हो जाता है। और मान लीजिए कि वह आंशिक पुनरावर्ती फलन जब भी μyR (y, x) परिभाषित होता है और y, μyR(y, x1, ..., xk) या उससे छोटा होता है, तो वह किसी चीज़ (शून्य की आवश्यकता नहीं) की ओर आगमन करता है। तब फलन μyR(y, x1, ..., xk) भी आंशिक पुनरावृत्ति फलन होता है।

μ-संचालक का उपयोग म्यू-रिकर्सिव फलन μ रिकर्सिव फलन के रूप में गणना योग्य फलन के लक्षण वर्णन में किया जाता है।

रचनात्मक गणित में, असीम सर्च संचालक मार्कोव के सिद्धांत से संबंधित होता है।

उदाहरण

उदाहरण 1: परिबद्ध μ-संचालक प्रारंभिक पुनरावर्ती फलन है

निम्नलिखित में 'x' स्ट्रिंग xi, ..., xn को प्रस्तुत करता है।

बंधे हुए μ-संचालक को दो प्रारंभिक पुनरावर्ती फलन (इसके बाद "पीआरएफ") के संदर्भ में व्यक्त किया जा सकता है, जिनका उपयोग स्थिति फलन को परिभाषित करने के लिए भी किया जाता है - उत्पाद-शब्दों का Π और योग-योग Σ (सीएफ क्लेन B पृष्ठ 224 की तुलना करें)। (जैसे-जैसे आवश्यकता होती है, कोई भी चरण जैसे s ≤ t या t < z, या 5 < x < 17 आदि चुन सकते हैं)। उदाहरण के लिए:

  • Πst fs(x, s) = f0(x, 0) × f1(x, 1) × ... × ft(x, t)
  • Σt<z gt(x, t) = g0(x, 0) + g1(x, 1) + ... + gz-1(x, z-1)

आगे बढ़ने से पहले हमें फलन ψ को "प्रतिनिदित करने वाला फलन" के रूप में परिचय देने की आवश्यकता है, जो प्रमेय R का है। फलन ψ को इनपुट (t = "सत्यता", f = "असत्यता") से आउटपुट (0, 1) तक परिभाषित किया जाता है (ध्यान दें अनुक्रम!)। इस स्थितियों में ψ के इनपुट, अर्थात {t, f}, प्रमेय R के आउटपुट से आ रहे हैं:

  • ψ(R = t) = 0
  • ψ(R = f) = 1

क्लेन दर्शाता है कि μyy<zR(y) निम्नलिखित रूप में परिभाषित होता है; हम देखते हैं कि उत्पाद फलन Π बूलियन OR संचालक की प्रकार काम कर रहा है, और योग फलन Σ किसी प्रकार बूलियन AND की प्रकार काम कर रहा है, किन्तु केवल {Σ≠0, Σ=0} नहीं किंतु {1, 0} नहीं पैदा कर रहा है:

μyy<zR(y) = Σt<zΠst ψ(R(x, t, s)) =
[ψ(x, 0, 0)] +
[ψ(x, 1, 0) × ψ(x, 1, 1)] +
[ψ(x, 2, 0) × ψ(x, 2, 1) × ψ(x, 2, 2)] +
...+
[ψ(x, z-1, 0) × ψ(x, z-1, 1) × ψ(x, z-1, 2) × . . . . . . . . × ψ(x, z-1, z-1)]
ध्यान दें कि Σ वास्तव में प्रारंभिक पुनरावृत्ति है जिसमें आधार Σ(x, 0) = 0 है और इंडक्शन स्टेप Σ(x, y+1) = Σ(x, y) + Π( x, y) है। उत्पाद Π भी प्रारंभिक पुनरावृत्ति है जिसमें आधार कदम Π(x, 0) = ψ(x, 0) होता है और इंडक्शन स्टेप Π(x, y+1) = Π(x, y) × ψ(x, y+1) होता है।

इस समीकरण को उदाहरण के साथ समझना आसान होता है, जैसा कि क्लीन द्वारा दिया गया है। उन्होंने प्रतिनिदित करने वाले फलन ψ(R(y)) के लिए एंट्रीज केवल तैयार की थीं। उन्होंने प्रतिनिदित करने वाले फलन के लिए χ(y) को ψ(x, y) के अतिरिक्त चिन्हित किया था।

y 0 1 2 3 4 5 6 7=z
χ(y) 1 1 1 0 1 0 0
π(y) = Πsy χ(s) 1 1 1 0 0 0 0 0
σ(y) = Σt<y π(t) 1 2 3 3 3 3 3 3
least y < z such that R(y) is "true":
φ(y) = μyy<zR(y)
3


उदाहरण 2: असीम μ-संचालक आदिम-पुनरावर्ती नहीं होता है

असीम μ-संचालक-फलन μy-वह है जिसे सामान्यतः ग्रंथों में परिभाषित किया गया है। किन्तु पाठक को आश्चर्य हो सकता है कि असंबद्ध μ-संचालक किसी अन्य प्राकृतिक संख्या के अतिरिक्त शून्य उत्पन्न करने के लिए फलन R('x', y) की अविष्कार क्यों कर रहा है।

फुटनोट में मिन्स्की अपने संचालक को तब समाप्त करने की अनुमति देता है जब अंदर का फलन पैरामीटर k से मेल खाता है; यह उदाहरण इसलिए भी उपयोगी है क्योंकि यह किसी अन्य लेखक का प्रारूप दिखाता है:
"μt[φ(t) = k]" (पृ. 210)

शून्य का कारण यह है कि असीम संचालक μy को फलन "उत्पाद" Π के संदर्भ में परिभाषित किया जाएगा, जिसमें निर्देशिका y को "बढ़ने" की अनुमति होती है जैसे-जैसे μ-संचालक अविष्कार करता है। जैसा कि ऊपर के उदाहरण में दिखाया गया है, स्ट्रिंग संख्याओं ψ(x, 0) *, ..., * ψ(x, y) का उत्पाद Πx<y कभी भी जब भी ψ(x, i) में से कोई भी सदस्य शून्य होता है, तो वह 0 प्राप्त करता है:

Πs<y = ψ(x, 0) * , ..., * ψ(x, y) = 0

यदि कोई ψ(x, i) = 0 जहां 0≤is है। इस प्रकार Π बूलियन AND की प्रकार फलन कर रहा है।

फलन μy "उत्पाद" के रूप में एकल प्राकृतिक संख्या y = {0, 1, 2, 3, ...} उत्पन्न करता है। चूँकि, संचालक के अंदर कुछ स्थितियों में से दिखाई दे सकती है: (a) "संख्या-सैद्धांतिक फलन" χ जो प्राकृतिक संख्या उत्पन्न करता है, या (b)"प्रतिलोम" R जो या {t = सत्य, f = असत्य} प्राप्त करता है। (और, आंशिक पुनरावर्ती फलन के संदर्भ में क्लेन ने बाद में तीसरा परिणाम की अनुमति देते हैं μ = निर्धारित")।[1] किया गया है।

क्लीन अपने असीमित μ-संचालक की परिभाषा को दो स्थितियों (a) और (b) को नियंत्रण करने के लिए विभाजित करते हैं। स्थिति (b) के लिए, पूर्व प्रतिनिदित फलन R(x, y) को उसके प्रतिनिदित फलन χ द्वारा पहले {t, f} से "ऑपरेट किया जाना" चाहिए, ताकि {0, 1} प्राप्त हो। और स्थिति (a) के लिए यदि परिभाषा का उपयोग किया जाना है तो संख्यात्मक फलन χ को शून्य प्राप्त करने के लिए "संतुष्ट" करना आवश्यक है। इस स्थितियों में, उन्होंने एकल "प्रूफ III" के साथ दिखाया है कि प्रकार (a) या (b) और पांच प्रारंभिक पुनरावृत्ति संचालक द्वारा जनित होने वाले (कुल) पुनरावृत्ति फलन को देते हैं, इस उल्लेख के साथ कि पूर्ण फलन के लिए:

सभी मापदंडों के लिए x, यह दिखाने के लिए प्रदर्शन प्रदान किया जाना चाहिए कि y उपस्थित है जो संतुष्ट करता है (ए) μyψ(x, y) या (बी) μyR(x, y),

क्लेन तीसरी स्थिति (सी) को भी स्वीकार करता है जिसके लिए सभी x के प्रदर्शन की आवश्यकता नहीं है, y उपस्थित है जैसे कि ψ(x, y)। वह अपने प्रमाण में इसका उपयोग करता है कि गिनाए जा सकने वाले फलन से अधिक कुल पुनरावर्ती फलन उपस्थित हैं; सी.एफ. फ़ुटनोट संपूर्ण फलन प्रदर्शन किया जाता है ।

क्लेन का प्रमाण अनौपचारिक है और पहले उदाहरण के समान उदाहरण का उपयोग करता है, किन्तु पहले वह μ-संचालक को अलग रूप में डालता है जो फलन χ पर काम करने वाले उत्पाद-शब्द Π का उपयोग करता है जो प्राकृतिक संख्या n उत्पन्न करता है, जो कोई भी प्राकृतिक संख्या हो सकती है, और उस स्थिति में 0 जब यू-संचालक का परीक्षण संतुष्ट हो जाता है।

परिभाषा Π-फलन के साथ पुनर्गठित होती है,
μyy<zχ(y) ==
  • (i): π('x', y) = πs<yχ(x, s)
  • (ii): φ(x) = τ(π(x, y), π(x, y' ), y)
  • (iii): τ(z' , 0, y) = y ;τ(u, v, w) u = 0 या v > 0 के लिए अपरिभाषित है।

यह सूक्ष्म है। पहली देखरेख में समीकरण प्रारंभिक पुनरावर्तन का उपयोग करते हुए प्रतीत होते हैं। किन्तु क्लेन ने हमें सामान्य रूप का आधार चरण और प्रेरण चरण प्रदान नहीं किया है,

  • आधार चरण: φ(0, x) = φ(x)
  • प्रेरण चरण: φ(0, x) = ψ(y, φ(0,x), x)

यह देखने के लिए कि क्या हो रहा है, हमें सबसे पहले स्वयं को याद दिलाना होगा कि हमने प्रत्येक चर x के लिए पैरामीटर ( प्राकृतिक संख्या) निर्दिष्ट किया है। दूसरा, हम उत्तराधिकारी-संचालक को काम पर y (अर्थात y' ) दोहराते हुए देखते हैं। और तीसरा, हम देखते हैं कि फलन μy y<zχ(y, x') केवल χ(y,x) अर्थात χ(0,x), χ(1,x), ... के उदाहरण उत्पन्न कर रहा है जब तक कि उदाहरण 0 प्राप्त न हो जाए। चौथा , जब उदाहरण χ(n, x) से 0 प्राप्त होता है तो यह τ के मध्य पद का कारण बनता है, अर्थात v = π(x, y ) से 0 प्राप्त होता है। अंत में, जब मध्य पद v = 0, μyy<zχ(y) होता है, लाइन (iii) निष्पादित करता है और बाहर निकलता है। क्लेन की समीकरणों (ii) और (iii) की प्रस्तुति का आदान-प्रदान इस बिंदु को बनाने के लिए किया गया है कि रेखा (iii) निकास का प्रतिनिधित्व करती है - निकास केवल तभी लिया जाता है जब अविष्कार सफलतापूर्वक χ(y) और मध्य उत्पाद-शब्द π को संतुष्ट करने के लिए y पाती है। ('x', y' ) 0 है; इसके बाद संचालक अपनी अविष्कार को τ(z', 0, y) = y के साथ समाप्त करता है।

τ(π('x', y), π('x', y' ), y), अर्थात:
  • τ(π('x', 0), π('x', 1), 0),
  • τ(π('x', 1), π('x', 2), 1)
  • τ(π('x', 2), π('x', 3), 2)
  • τ(π('x', 3), π('x', 4), 3)
  • ... जब तक कोई मिलान y=n पर न हो जाए और तब,
  • τ(z' , 0, y) = τ(z' , 0, n) = n और μ-संचालक की अविष्कार पूरी हो गई है।

उदाहरण के लिए क्लेन (xi, ..., xn) के किसी भी निश्चित मान पर विचार करें और 'χ(x) के लिए बस 'χ(xi, ..., xn), y)'":

y 0 1 2 3 4 5 6 7 etc.
χ(y) 3 1 2 0 9 0 1 5 . . .
π(y) = Πsyχ(s) 1 3 3 6 0 0 0 0 . . .
least y < z such that R(y) is "true":
φ(y) = μyy<zR(y)
3
  1. pp. 332ff