Μ ऑपरेटर

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

परिभाषा

मान लीजिए कि 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)) निम्नलिखित रूप में:

$(\exists \mu ^{2})(\forall f^{1}){\big (}(\exists n^{0})(f(n)=0)\rightarrow f(\mu (f))=0{\big )},$

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

गुण

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

μy_y<zR(y, x₁, ..., x_n) प्रारंभिक पुनरावृत्ति फलन है।

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

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

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

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

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

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

उदाहरण

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

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

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

• Π_s≤t f_s(x, s) = f₀(x, 0) × f₁(x, 1) × ... × f_t(x, t)
• Σ_t<z g_t(x, t) = g₀(x, 0) + g₁(x, 1) + ... + g_z-1(x, z-1)

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

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

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

μy_y<zR(y) = Σ_t<zΠ_s≤t ψ(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) = Πs≤y χ(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≤i≤s है। इस प्रकार Π बूलियन AND की प्रकार फलन कर रहा है।

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

क्लीन अपने असीमित μ-संचालक की परिभाषा को दो स्थितियों (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 जब यू-संचालक का परीक्षण संतुष्ट हो जाता है।

परिभाषा Π-फलन के साथ पुनर्गठित होती है,

μy_y<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, μy_y<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 और μ-संचालक की खोज पूरी हो गई है।

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

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