View source for Μ ऑपरेटर

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

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

घिरे μ-संचालक पहले क्लेन (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)

[[स्टीफन क्लेन]] का कहना है कि चर 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} में परिवर्तित करता है।

अध्याय XI §57 सामान्य पुनरावर्ती कार्यों में, क्लेन निम्नलिखित विधि से चर y पर असीम μ-संचालक को परिभाषित करता है,
:<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(y) के लिए असीम μ-संचालक μyR(y) (नोट (Ey) के लिए कोई आवश्यकता नहीं) एक आंशिक फलन है। इसके अतिरिक्त क्लेन इसे एक संपूर्ण फलन के रूप में बनाता है (cf. पृष्ठ 317):

<math> \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}</math>"" 

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

<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}}

== गुण ==

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

<!--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: परिबद्ध μ-संचालक एक आदिम पुनरावर्ती फलन है ===

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

बंधे हुए μ-संचालक को दो आदिम पुनरावर्ती कार्यों (इसके बाद पीआरएफ) के संदर्भ में व्यक्त किया जा सकता है, जिनका उपयोग स्थिति फलन को परिभाषित करने के लिए भी किया जाता है - उत्पाद-शब्दों का Π और योग-योग Σ (सीएफ क्लेन #) बी पेज 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>''t''<''z''</sub> g<sub>''t''</sub>(एक्स, ''टी'') = जी<sub>0</sub>(एक्स, 0) + जी<sub>1</sub>(एक्स, 1) + ... + जी<sub>z-1</sub>(एक्स, ''जेड''-1)

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

क्लेन दर्शाता है कि μ''y''<sub>''y''<''z''</sub>R(y) को इस प्रकार परिभाषित किया गया है; हम देखते हैं कि उत्पाद फलन Π एक बूलियन या संचालक की तरह कार्य कर रहा है, और योग Σ कुछ सीमा तक बूलियन और की तरह कार्य कर रहा है, किन्तु केवल {1, 0} के अतिरिक्त {Σ≠0, Σ=0} उत्पन्न कर रहा है:
: μy<sub>''y''<''z''</sub>आर(वाई) = एस<sub>''t''<''z''</sub>Π<sub>''s''≤''t''</sub> ψ(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'') निर्दिष्ट किया:
{| class="wikitable" style="text-align: center; vertical-align: bottom;"
|-
! width="209"| ''y''
! width="24"| 0
! width="24"| 1
! width="24"| 2
!style="background-color:#C0C0C0;" width="24"| '''3'''
! width="24"| 4
! width="24"| 5
! width="24"| 6
! width="25.2"| 7=''z''
|-
! χ(''y'')
| 1
| 1
| 1
|style="background-color:#C0C0C0;font-weight:bold"| 0
| 1
| 0
| 0
| 
|-
! π(''y'') = Π<sub>''s''≤''y''</sub> χ(''s'')
| 1
| 1
| 1
|style="background-color:#C0C0C0;font-weight:bold"| 0
| 0
| 0
| 0
| 0
|-
! σ(''y'') = Σ<sub>''t''<''y''</sub> π(''t'')
| 1
| 2
| 3
|style="background-color:#C0C0C0;"| '''3'''
| 3
| 3
| 3
| 3
|-
! least ''y'' < ''z'' such that R(''y'') is "true":<br/>φ(''y'') = μ''y''<sub>''y''<''z''</sub>R(''y'')
| 
| 
| 
|style="background-color:#C0C0C0;font-weight:bold" | 3
| 
| 
| 
| 
|}


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

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

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

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

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

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

: परिभाषा Π-फलन के साथ पुनर्गठित होती है:
:μ''y''<sub>''y''<''z''</sub>एक्स(वाई) =
:*(i): π('x', y) = π<sub>''s''<''y''</sub>χ(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'' के लिए एक पैरामीटर (एक प्राकृतिक संख्या) निर्दिष्ट किया है।<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), π('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) के किसी भी निश्चित मान पर विचार करें<sub>''i''</sub>, ..., एक्स<sub>''n''</sub>) और 'χ(x) के लिए बस 'χ(y)' लिखें<sub>''i''</sub>, ..., एक्स<sub>''n''</sub>), और)' :
{| class="wikitable" style="text-align: center; vertical-align: bottom;"
|-
! width="208.8"| ''y''
! width="24"| 0
! width="24"| 1
! width="24"| 2
!style="background-color:#C0C0C0;" width="24"| '''3'''
! width="24"| 4
! width="24"| 5
! width="24"| 6
! width="25.2"| 7
! width="25.2"| etc.
|-
! χ(''y'')
| 3
| 1
| 2
|style="background-color:#C0C0C0;"| '''0'''
| 9
| 0
| 1
| 5
|style="font-weight:bold"|  . . .
|-
! π(''y'') = Π<sub>''s''≤''y''</sub>χ(''s'')
| 1
| 3
| 3
|style="background-color:#C0C0C0;"| '''6'''
| 0
| 0
| 0
| 0
|style="font-weight:bold"|  . . .
|-
!
| 
| 
| 
|style="background-color:#C0C0C0"| '''↑'''
| 
| 
| 
| 
| 
|-
! least ''y'' < ''z'' such that R(''y'') is "true":<br/>φ(''y'') = μ''y''<sub>''y''<''z''</sub>R(''y'')
| 
| 
| 
|style="background-color:#C0C0C0;font-weight:bold"| 3
| 
| 
| 
| 
| 
|}
<!--

=== उदाहरण 3: एक अमूर्त मशीन के संदर्भ में असीमित μ-ऑपरेटर की परिभाषा ===

दोनों मिन्स्की (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]]