μ ऑपरेटर

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

परिभाषा

मान लीजिए कि 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}}$ अनबाउंड μ-ऑपरेटर के कुल संस्करण का अध्ययन उच्च-क्रम रिवर्स गणित में किया जाता है (Kohlenbach (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.

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

• Π_s≤t f_s(एक्स, एस) = एफ₀(एक्स, 0) × एफ₁(एक्स, 1) × ... × एफ_t(एक्स, टी)
• एस_t<z g_t(एक्स, टी) = जी₀(एक्स, 0) + जी₁(एक्स, 1) + ... + जी_z-1(एक्स, जेड-1)

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

• ψ(आर = टी) = 0
• ψ(आर = एफ) = 1

क्लेन दर्शाता है कि μy_y<zR(y) को इस प्रकार परिभाषित किया गया है; हम देखते हैं कि उत्पाद फ़ंक्शन Π एक बूलियन या ऑपरेटर की तरह कार्य कर रहा है, और योग Σ कुछ हद तक बूलियन AND की तरह कार्य कर रहा है, लेकिन केवल {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 है। इस प्रकार Π एक बूलियन AND की तरह कार्य कर रहा है।

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

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

सभी मापदंडों के लिए 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 के लिए एक पैरामीटर (एक प्राकृतिक संख्या) निर्दिष्ट किया है।_i. दूसरा, हम एक उत्तराधिकारी-ऑपरेटर को काम पर 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