Μ ऑपरेटर: Difference between revisions

Revision as of 11:32, 9 August 2023

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

परिभाषा

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

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

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

(पृ. 225)

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

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

(\exists y)\mu yR(y)=\{{\mbox{the least (natural number)}}\ y\ {\mbox{such that}}\ R(y)\}

(पृ. 279, कहां

(\exists y)

इसका कारण है कि कोई ऐसा अस्तित्व है कि... )

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

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

$\varepsilon yR(x,y)={\begin{cases}{\text{the least }}y{\text{ such that }}R(x,y),&{\text{if }}(Ey)R(x,y)\\0,&{\text{otherwise}}.\end{cases}}$ ""

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

${\displaystyle ($

@@ Line 7: / Line 7: @@
 :<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। "जब सूचित श्रेणी में R(y) [सत्य होने] वाले कोई 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 "सामान्य पुनरावर्ती फलन में", क्लीन ने चरण से निर्धारित असीमित μ-संचालक को निम्नलिखित तरीके से परिभाषित किया है,
-:<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)" की कोई आवश्यकता नहीं है) आंशिक फलन है। क्लीन ने इसे इसके अतिरिक्त पूर्ण फलन के रूप में बदला है (पृ. 317):
@@ Line 29: / Line 29: @@
 == गुण ==
-(i) [[आदिम पुनरावर्ती कार्य|प्रारंभिक पुनरावर्ती]] फलन के संदर्भ में, जहां μ-संचालक का खोज चर y घिरा हुआ है, उदाहरण के लिए y < z नीचे दिए गए सूत्र में, यदि विधेय R प्रारंभिक पुनरावर्ती है (क्लीन प्रूफ़ #E पृष्ठ 228), तो
+(i) [[आदिम पुनरावर्ती कार्य|प्रारंभिक पुनरावर्ती]] फलन के संदर्भ में, जहां μ-संचालक का खोज चर y घिरा हुआ है, उदाहरण के लिए y < z नीचे दिए गए सूत्र में, यदि विधेय R प्रारंभिक पुनरावर्ती है (क्लीन प्रूफ़ E पृष्ठ 228), तो
 : μ''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> के लिए उपस्थित होने की गारंटी है कुल पुनरावर्ती विधेय आर के पैरामीटर,
-:(''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 का मौजूद होना" का अर्थ होता है (Kleene (1952) पृ. 279 का अनुकरण करें।)
+:(''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 का अनुकरण करें।)
-इसके बाद पांच प्रारंभिक पुनरावर्ती संचालक और असीमित-किन्तु-कुल μ-संचालक "सामान्य" पुनरावृत्ति फलन की उत्पन्न करते हैं (यानी छह पुनरावृत्ति संचालक द्वारा परिभाषित पूरे फलन का समूह)।
+इसके बाद पांच प्रारंभिक पुनरावर्ती संचालक और असीमित-किन्तु-कुल μ-संचालक "सामान्य" पुनरावृत्ति फलन की उत्पन्न करते हैं (अर्थात छह पुनरावृत्ति संचालक द्वारा परिभाषित पूरे फलन का समूह)।
 (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>'') भी आंशिक पुनरावृत्ति फलन होता है।
@@ Line 53: / Line 53: @@
 :*Σ<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)
-आगे बढ़ने से पहले हमें फलन ψ को "प्रतिनिदित करने वाला फलन" के रूप में परिचय देने की आवश्यकता है, जो प्रमेय R का है। फलन ψ को इनपुट (t = "सत्यता", f = "असत्यता") से आउटपुट (0, 1) तक परिभाषित किया जाता है (ध्यान दें अनुक्रम!)। इस स्थितियों में ψ के इनपुट, यानी {t, f}, प्रमेय R के आउटपुट से आ रहे हैं:
+आगे बढ़ने से पहले हमें फलन ψ को "प्रतिनिदित करने वाला फलन" के रूप में परिचय देने की आवश्यकता है, जो प्रमेय R का है। फलन ψ को इनपुट (t = "सत्यता", f = "असत्यता") से आउटपुट (0, 1) तक परिभाषित किया जाता है (ध्यान दें अनुक्रम!)। इस स्थितियों में ψ के इनपुट, अर्थात {t, f}, प्रमेय R के आउटपुट से आ रहे हैं:
 :* ψ(R = t) = 0
 :* ψ(R = f) = 1
-क्लेन दर्शाता है कि μ''y''<sub>''y''<''z''</sub>R(y) निम्नलिखित रूप में परिभाषित होता है; हम देखते हैं कि उत्पाद फलन Π बूलियन OR संचालक की तरह काम कर रहा है, और योग फलन Σ किसी प्रकार बूलियन AND की तरह काम कर रहा है, लेकिन केवल {Σ≠0, Σ=0} नहीं बल्कि {1, 0} नहीं पैदा कर रहा है:
+क्लेन दर्शाता है कि μ''y''<sub>''y''<''z''</sub>R(y) निम्नलिखित रूप में परिभाषित होता है; हम देखते हैं कि उत्पाद फलन Π बूलियन OR संचालक की प्रकार काम कर रहा है, और योग फलन Σ किसी प्रकार बूलियन AND की प्रकार काम कर रहा है, किन्तु केवल {Σ≠0, Σ=0} नहीं बल्कि {1, 0} नहीं पैदा कर रहा है:
 : μ''y<sub>y</sub>''<sub><''z''</sub>R(''y'') = Σ<sub>''t''<''z''</sub>Π<sub>''s''≤''t''</sub> ψ(R('''x''', ''t'', ''s'')) =
 : [ψ(x, 0, 0)] +
@@ Line 130: / Line 130: @@
 :Π<sub>''s''<''y''</sub> = ψ(x, 0) * , ..., * ψ(x, ''y'') = 0
-यदि कोई ψ(x, ''i'') = 0 जहां 0≤''i''≤''s'' है। इस प्रकार Π बूलियन AND की तरह फलन कर रहा है।
+यदि कोई ψ(x, ''i'') = 0 जहां 0≤''i''≤''s'' है। इस प्रकार Π बूलियन AND की प्रकार फलन कर रहा है।
 फलन μ''y'' "उत्पाद" के रूप में एकल प्राकृतिक संख्या ''y'' = {0, 1, 2, 3, ...} उत्पन्न करता है। चूँकि, संचालक के अंदर कुछ स्थितियों में से दिखाई दे सकती है: (a) "संख्या-सैद्धांतिक फलन" χ जो प्राकृतिक संख्या उत्पन्न करता है, या (b)"प्रतिलोम" R जो या {t = सत्य, f = असत्य} प्राप्त करता है। (और, ''आंशिक'' पुनरावर्ती फलन के संदर्भ में क्लेन ने बाद में तीसरा परिणाम की अनुमति देते हैं μ = निर्धारित")।<ref>pp.&nbsp;332ff</ref> किया गया है।
@@ Line 146: / Line 146: @@
 :*(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'' <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</sub>''<sub><''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', 0), π('x', 1), 0),

Anonymous

Search

Μ ऑपरेटर: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:32, 9 August 2023

Contents

परिभाषा