Μ ऑपरेटर

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

परिभाषा

मान लीजिए कि R(y, 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। जब संकेतित श्रेणी में कोई y नहीं है जैसे कि R(y) [ सत्य है ], तो μy अभिव्यक्ति का मान श्रेणी की बुनियादी संख्या है (पृष्ठ 226); यही कारण है कि उपरोक्त परिभाषा में गलती z दिखाई देता है। जैसा कि नीचे दिखाया गया है, परिबद्ध μ-संचालक μy_y<z इसे दो आदिम पुनरावर्ती कार्यों के संदर्भ में परिभाषित किया गया है जिन्हें परिमित योग Σ और परिमित उत्पाद Π कहा जाता है, एक विधेय फलन जो परीक्षण करता है और एक प्रतिनिधित्व फलन जो {t, f} को {0, 1} में परिवर्तित करता है।

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

$(\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) के लिए कोई आवश्यकता नहीं) एक आंशिक फलन है। इसके अतिरिक्त क्लेन इसे एक संपूर्ण फलन के रूप में बनाता है (cf. पृष्ठ 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|ACA को जन्म देता है जब इसे उच्च-क्रम विपरीत गणित के सामान्य आधार सिद्धांत के साथ जोड़ा जाता है।

गुण

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

μy_y<zआर(य, एक्स₁, ..., एक्स_n) एक आदिम पुनरावर्ती कार्य है।

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

(एक्स₁),...,(एक्स_n) (आई) आर(वाई, एक्स_i, ..., एक्स_n) का तात्पर्य है कि μyR(y, x_i, ..., एक्स_n) एक पूर्ण पुनरावर्ती कार्य है।

यहाँ (x_i) का मतलब सभी x के लिए है_iऔर आई का मतलब है कि वाई का कम से कम एक मान उपस्थित है जैसे... (सीएफ क्लेन (1952) पृष्ठ 279।)

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

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

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

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

उदाहरण

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

निम्नलिखित में 'x' स्ट्रिंग x को दर्शाता है_i, ..., एक्स_n.

बंधे हुए μ-संचालक को दो आदिम पुनरावर्ती कार्यों (इसके बाद पीआरएफ) के संदर्भ में व्यक्त किया जा सकता है, जिनका उपयोग स्थिति फलन को परिभाषित करने के लिए भी किया जाता है - उत्पाद-शब्दों का Π और योग-योग Σ (सीएफ क्लेन #) बी पेज 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)

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

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

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

μy_y<zआर(वाई) = एस_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) के लिए प्रविष्टियां बनाईं। उन्होंने ψ(x, y के अतिरिक्त प्रतिनिधित्व करने वाले कार्यों को χ(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<y संख्याओं ψ(x, 0) *, ..., * ψ(x, y) की एक स्ट्रिंग में शून्य प्राप्त होता है जब भी इसके सदस्यों में से एक ψ(x, i) शून्य होता है|

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

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

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

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

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

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

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

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

μy_y<zएक्स(वाई) =

• (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, ..., एक्स_n) और 'χ(x) के लिए बस 'χ(y)' लिखें_i, ..., एक्स_n), और)

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