बीटा सामान्य रूप: Difference between revisions
From Vigyanwiki
(Created page with "लैम्ब्डा कैलकुलस में, यदि कोई ''लैम्ब्डा कैलकुलस#β-रिडक्शन'' संभव न...") |
No edit summary |
||
| Line 1: | Line 1: | ||
[[लैम्ब्डा कैलकुलस]] में, यदि कोई ''लैम्ब्डा कैलकुलस | [[लैम्ब्डा कैलकुलस]] में, यदि कोई ''लैम्ब्डा कैलकुलस β-रिडक्शन'' संभव नहीं है, तो शब्द बीटा सामान्य रूप में होता है।<ref>{{cite encyclopedia| url=http://encyclopedia2.thefreedictionary.com/Beta+normal+form | title=बीटा सामान्य रूप| encyclopedia=Encyclopedia | publisher=[[TheFreeDictionary.com]] |accessdate=18 November 2013 }}</ref> शब्द बीटा-एटा सामान्य रूप में होता है यदि न तो बीटा कमी और न ही ''लैम्ब्डा कैलकुलस η-कमी'' संभव है। यदि ''हेड पोजीशन में बीटा-रेडेक्स'' नहीं है तो शब्द हेड सामान्य रूप में होता है। किसी शब्द का सामान्य रूप, यदि कोई मौजूद है, अद्वितीय है (चर्च-रोसेर प्रमेय के परिणाम के रूप में)।<ref>{{Cite book |last=Thompson |first=Simon |url=https://www.worldcat.org/oclc/23287456 |title=प्रकार सिद्धांत और कार्यात्मक प्रोग्रामिंग|date=1991 |publisher=Addison-Wesley |isbn=0-201-41667-0 |location=Wokingham, England |pages=38 |oclc=23287456}}</ref> हालाँकि, शब्द के से अधिक शीर्ष सामान्य रूप हो सकते हैं। | ||
==बीटा कमी== | ==बीटा कमी== | ||
लैम्ब्डा कैलकुलस में, बीटा रिडेक्स फॉर्म का | लैम्ब्डा कैलकुलस में, बीटा रिडेक्स फॉर्म का शब्द है:<ref name=":0">{{Cite book |last=Barendregt |first=Henk P. |url=https://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf |title=लैम्ब्डा कैलकुलस का परिचय|year=1984 |edition=Revised |pages=24}}</ref><ref>{{Cite book |last=Thompson |first=Simon |url=https://www.worldcat.org/oclc/23287456 |title=प्रकार सिद्धांत और कार्यात्मक प्रोग्रामिंग|date=1991 |publisher=Addison-Wesley |isbn=0-201-41667-0 |location=Wokingham, England |pages=35 |oclc=23287456}}</ref> | ||
:<math> (\mathbf{\lambda} x . A) M</math>. | :<math> (\mathbf{\lambda} x . A) M</math>. | ||
एक रेडेक्स <math>r</math> | एक रेडेक्स <math>r</math> पद में शीर्ष स्थान पर है <math>t</math>, अगर <math>t</math> इसका आकार निम्नलिखित है (ध्यान दें कि अनुप्रयोग की प्राथमिकता अमूर्तता से अधिक है, और नीचे दिए गए सूत्र का अर्थ लैम्ब्डा-अमूर्त होना है, अनुप्रयोग नहीं): | ||
:<math> \lambda x_1 \ldots \lambda x_n . \underbrace{(\lambda x . A) M_1}_{\text{the redex }r} M_2 \ldots M_m </math>, कहाँ <math>n \geq 0</math> और <math>m \geq 1</math>. | :<math> \lambda x_1 \ldots \lambda x_n . \underbrace{(\lambda x . A) M_1}_{\text{the redex }r} M_2 \ldots M_m </math>, कहाँ <math>n \geq 0</math> और <math>m \geq 1</math>. | ||
बीटा कमी | बीटा कमी शब्द में निहित बीटा रिडेक्स के लिए निम्नलिखित पुनर्लेखन नियम का अनुप्रयोग है: | ||
:<math> (\mathbf{\lambda} x . A) M \longrightarrow A[x := M] </math> | :<math> (\mathbf{\lambda} x . A) M \longrightarrow A[x := M] </math> | ||
कहाँ <math>A[x := M]</math> शब्द को प्रतिस्थापित करने का परिणाम है <math>M</math> चर के लिए <math>x</math> अवधि में <math>A</math>. | कहाँ <math>A[x := M]</math> शब्द को प्रतिस्थापित करने का परिणाम है <math>M</math> चर के लिए <math>x</math> अवधि में <math>A</math>. | ||
हेड बीटा रिडक्शन | हेड बीटा रिडक्शन बीटा रिडक्शन है जिसे हेड पोजीशन में लागू किया जाता है, जो कि निम्नलिखित रूप में होता है: | ||
:<math> \lambda x_1 \ldots \lambda x_n . (\lambda x . A) M_1 M_2 \ldots M_m \longrightarrow | :<math> \lambda x_1 \ldots \lambda x_n . (\lambda x . A) M_1 M_2 \ldots M_m \longrightarrow | ||
| Line 21: | Line 21: | ||
कोई भी अन्य कमी आंतरिक बीटा कमी है। | कोई भी अन्य कमी आंतरिक बीटा कमी है। | ||
'सामान्य रूप' | 'सामान्य रूप' ऐसा शब्द है जिसमें कोई बीटा रेडेक्स नहीं होता है,<ref name=":0" /><ref name=":1">{{Cite book |last=Thompson |first=Simon |url=https://www.worldcat.org/oclc/23287456 |title=प्रकार सिद्धांत और कार्यात्मक प्रोग्रामिंग|date=1991 |publisher=Addison-Wesley |isbn=0-201-41667-0 |location=Wokingham, England |pages=36 |oclc=23287456}}</ref> यानी उसे और कम नहीं किया जा सकता. 'हेड नॉर्मल फॉर्म' ऐसा शब्द है जिसमें हेड पोजीशन में बीटा रिडेक्स शामिल नहीं होता है, यानी इसे हेड रिडक्शन द्वारा और कम नहीं किया जा सकता है। सरल लैम्ब्डा कैलकुलस पर विचार करते समय (अर्थात स्थिरांक या फ़ंक्शन प्रतीकों को जोड़े बिना, जिसका अर्थ अतिरिक्त डेल्टा नियम द्वारा कम किया जाना है), शीर्ष सामान्य रूप निम्नलिखित आकार के शब्द हैं: | ||
:<math> \lambda x_1 \ldots \lambda x_n . x M_1 M_2 \ldots M_m </math>, कहाँ <math>x</math> | :<math> \lambda x_1 \ldots \lambda x_n . x M_1 M_2 \ldots M_m </math>, कहाँ <math>x</math> परिवर्तनशील है, <math>n \geq 0</math> और <math>m \geq 0</math>. | ||
सिर का सामान्य रूप हमेशा सामान्य रूप नहीं होता,<ref name=":1" />क्योंकि लागू तर्क <math>M_j</math> सामान्य होने की आवश्यकता नहीं है. हालाँकि, इसका उलटा सच है: कोई भी सामान्य रूप भी | सिर का सामान्य रूप हमेशा सामान्य रूप नहीं होता,<ref name=":1" />क्योंकि लागू तर्क <math>M_j</math> सामान्य होने की आवश्यकता नहीं है. हालाँकि, इसका उलटा सच है: कोई भी सामान्य रूप भी प्रमुख सामान्य रूप है।<ref name=":1" />वास्तव में, सामान्य रूप बिल्कुल शीर्ष सामान्य रूप होते हैं जिनमें उपपद होते हैं <math>M_j</math> स्वयं सामान्य रूप हैं। यह सामान्य रूपों का आगमनात्मक वाक्यविन्यास विवरण देता है। | ||
कमजोर शीर्ष सामान्य रूप की भी धारणा है: कमजोर शीर्ष सामान्य रूप में | कमजोर शीर्ष सामान्य रूप की भी धारणा है: कमजोर शीर्ष सामान्य रूप में शब्द या तो सिर सामान्य रूप में शब्द है या लैम्ब्डा अमूर्त है।<ref>{{cite encyclopedia| url=http://encyclopedia2.thefreedictionary.com/Weak+Head+Normal+Form | title=कमजोर सिर सामान्य रूप| encyclopedia=Encyclopedia | publisher=[[TheFreeDictionary.com]] |accessdate=30 April 2021 }}</ref> इसका मतलब है कि लैम्ब्डा बॉडी के अंदर रेडेक्स दिखाई दे सकता है। | ||
==कमी की रणनीतियाँ== | ==कमी की रणनीतियाँ== | ||
सामान्य तौर पर, किसी दिए गए शब्द में कई रिडेक्स शामिल हो सकते हैं, इसलिए कई अलग-अलग बीटा कटौती लागू की जा सकती हैं। हम किस रिडेक्स को कम करना है यह चुनने के लिए कटौती रणनीति (लैम्ब्डा कैलकुलस) निर्दिष्ट कर सकते हैं। | |||
सामान्य तौर पर, किसी दिए गए शब्द में कई रिडेक्स शामिल हो सकते हैं, इसलिए कई अलग-अलग बीटा कटौती लागू की जा सकती हैं। हम किस रिडेक्स को कम करना है यह चुनने के लिए | |||
* सामान्य-क्रम कटौती वह रणनीति है जिसमें व्यक्ति सिर की स्थिति में बीटा कमी के नियम को लगातार लागू करता है जब तक कि ऐसी और कटौती संभव न हो जाए। उस बिंदु पर, परिणामी पद सामान्य रूप में होता है। फिर कोई उपशर्तों में हेड रिडक्शन लागू करना जारी रखता है <math>M_j</math>, बाएं से दाएं। अन्यथा कहा गया है, सामान्य-क्रम कटौती वह रणनीति है जो हमेशा सबसे पहले बाएं-सबसे बाहरी-सबसे रिडेक्स को कम करती है। | * सामान्य-क्रम कटौती वह रणनीति है जिसमें व्यक्ति सिर की स्थिति में बीटा कमी के नियम को लगातार लागू करता है जब तक कि ऐसी और कटौती संभव न हो जाए। उस बिंदु पर, परिणामी पद सामान्य रूप में होता है। फिर कोई उपशर्तों में हेड रिडक्शन लागू करना जारी रखता है <math>M_j</math>, बाएं से दाएं। अन्यथा कहा गया है, सामान्य-क्रम कटौती वह रणनीति है जो हमेशा सबसे पहले बाएं-सबसे बाहरी-सबसे रिडेक्स को कम करती है। | ||
* इसके विपरीत, एप्लिकेटिव ऑर्डर कटौती में, कोई पहले आंतरिक कटौती लागू करता है, और उसके बाद केवल हेड कटौती लागू करता है जब कोई और आंतरिक कटौती संभव नहीं होती है। | * इसके विपरीत, एप्लिकेटिव ऑर्डर कटौती में, कोई पहले आंतरिक कटौती लागू करता है, और उसके बाद केवल हेड कटौती लागू करता है जब कोई और आंतरिक कटौती संभव नहीं होती है। | ||
सामान्य-क्रम में कमी इस अर्थ में पूर्ण है कि यदि किसी पद का शीर्ष सामान्य रूप है, तो सामान्य-क्रम में कमी अंततः उस तक पहुंच जाएगी। उपरोक्त सामान्य रूपों के वाक्यविन्यास विवरण के अनुसार, इसमें "पूरी तरह से" सामान्य रूप के लिए | सामान्य-क्रम में कमी इस अर्थ में पूर्ण है कि यदि किसी पद का शीर्ष सामान्य रूप है, तो सामान्य-क्रम में कमी अंततः उस तक पहुंच जाएगी। उपरोक्त सामान्य रूपों के वाक्यविन्यास विवरण के अनुसार, इसमें "पूरी तरह से" सामान्य रूप के लिए ही कथन शामिल है (यह [[मानकीकरण प्रमेय]] है)। इसके विपरीत, लागू आदेश में कमी समाप्त नहीं हो सकती है, भले ही शब्द का सामान्य रूप हो। उदाहरण के लिए, एप्लिकेटिव ऑर्डर कटौती का उपयोग करते हुए, कटौती का निम्नलिखित क्रम संभव है: | ||
:<math>\begin{align} | :<math>\begin{align} | ||
| Line 49: | Line 48: | ||
:<math> (\mathbf{\lambda} x . z) ((\lambda w. w w w) (\lambda w. w w w)) </math> | :<math> (\mathbf{\lambda} x . z) ((\lambda w. w w w) (\lambda w. w w w)) </math> | ||
:<math> \rightarrow z </math> | :<math> \rightarrow z </math> | ||
सिनोट के [[ निर्देशक स्ट्रिंग ]]्स | सिनोट के [[ निर्देशक स्ट्रिंग |निर्देशक स्ट्रिंग]] ्स ऐसी विधि है जिसके द्वारा बीटा कमी की कम्प्यूटेशनल जटिलता को अनुकूलित किया जा सकता है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
Revision as of 15:28, 16 July 2023
लैम्ब्डा कैलकुलस में, यदि कोई लैम्ब्डा कैलकुलस β-रिडक्शन संभव नहीं है, तो शब्द बीटा सामान्य रूप में होता है।[1] शब्द बीटा-एटा सामान्य रूप में होता है यदि न तो बीटा कमी और न ही लैम्ब्डा कैलकुलस η-कमी संभव है। यदि हेड पोजीशन में बीटा-रेडेक्स नहीं है तो शब्द हेड सामान्य रूप में होता है। किसी शब्द का सामान्य रूप, यदि कोई मौजूद है, अद्वितीय है (चर्च-रोसेर प्रमेय के परिणाम के रूप में)।[2] हालाँकि, शब्द के से अधिक शीर्ष सामान्य रूप हो सकते हैं।
बीटा कमी
लैम्ब्डा कैलकुलस में, बीटा रिडेक्स फॉर्म का शब्द है:[3][4]
- .
एक रेडेक्स पद में शीर्ष स्थान पर है , अगर इसका आकार निम्नलिखित है (ध्यान दें कि अनुप्रयोग की प्राथमिकता अमूर्तता से अधिक है, और नीचे दिए गए सूत्र का अर्थ लैम्ब्डा-अमूर्त होना है, अनुप्रयोग नहीं):
- , कहाँ और .
बीटा कमी शब्द में निहित बीटा रिडेक्स के लिए निम्नलिखित पुनर्लेखन नियम का अनुप्रयोग है:
कहाँ शब्द को प्रतिस्थापित करने का परिणाम है चर के लिए अवधि में .
हेड बीटा रिडक्शन बीटा रिडक्शन है जिसे हेड पोजीशन में लागू किया जाता है, जो कि निम्नलिखित रूप में होता है:
- , कहाँ और .
कोई भी अन्य कमी आंतरिक बीटा कमी है।
'सामान्य रूप' ऐसा शब्द है जिसमें कोई बीटा रेडेक्स नहीं होता है,[3][5] यानी उसे और कम नहीं किया जा सकता. 'हेड नॉर्मल फॉर्म' ऐसा शब्द है जिसमें हेड पोजीशन में बीटा रिडेक्स शामिल नहीं होता है, यानी इसे हेड रिडक्शन द्वारा और कम नहीं किया जा सकता है। सरल लैम्ब्डा कैलकुलस पर विचार करते समय (अर्थात स्थिरांक या फ़ंक्शन प्रतीकों को जोड़े बिना, जिसका अर्थ अतिरिक्त डेल्टा नियम द्वारा कम किया जाना है), शीर्ष सामान्य रूप निम्नलिखित आकार के शब्द हैं:
- , कहाँ परिवर्तनशील है, और .
सिर का सामान्य रूप हमेशा सामान्य रूप नहीं होता,[5]क्योंकि लागू तर्क सामान्य होने की आवश्यकता नहीं है. हालाँकि, इसका उलटा सच है: कोई भी सामान्य रूप भी प्रमुख सामान्य रूप है।[5]वास्तव में, सामान्य रूप बिल्कुल शीर्ष सामान्य रूप होते हैं जिनमें उपपद होते हैं स्वयं सामान्य रूप हैं। यह सामान्य रूपों का आगमनात्मक वाक्यविन्यास विवरण देता है।
कमजोर शीर्ष सामान्य रूप की भी धारणा है: कमजोर शीर्ष सामान्य रूप में शब्द या तो सिर सामान्य रूप में शब्द है या लैम्ब्डा अमूर्त है।[6] इसका मतलब है कि लैम्ब्डा बॉडी के अंदर रेडेक्स दिखाई दे सकता है।
कमी की रणनीतियाँ
सामान्य तौर पर, किसी दिए गए शब्द में कई रिडेक्स शामिल हो सकते हैं, इसलिए कई अलग-अलग बीटा कटौती लागू की जा सकती हैं। हम किस रिडेक्स को कम करना है यह चुनने के लिए कटौती रणनीति (लैम्ब्डा कैलकुलस) निर्दिष्ट कर सकते हैं।
- सामान्य-क्रम कटौती वह रणनीति है जिसमें व्यक्ति सिर की स्थिति में बीटा कमी के नियम को लगातार लागू करता है जब तक कि ऐसी और कटौती संभव न हो जाए। उस बिंदु पर, परिणामी पद सामान्य रूप में होता है। फिर कोई उपशर्तों में हेड रिडक्शन लागू करना जारी रखता है , बाएं से दाएं। अन्यथा कहा गया है, सामान्य-क्रम कटौती वह रणनीति है जो हमेशा सबसे पहले बाएं-सबसे बाहरी-सबसे रिडेक्स को कम करती है।
- इसके विपरीत, एप्लिकेटिव ऑर्डर कटौती में, कोई पहले आंतरिक कटौती लागू करता है, और उसके बाद केवल हेड कटौती लागू करता है जब कोई और आंतरिक कटौती संभव नहीं होती है।
सामान्य-क्रम में कमी इस अर्थ में पूर्ण है कि यदि किसी पद का शीर्ष सामान्य रूप है, तो सामान्य-क्रम में कमी अंततः उस तक पहुंच जाएगी। उपरोक्त सामान्य रूपों के वाक्यविन्यास विवरण के अनुसार, इसमें "पूरी तरह से" सामान्य रूप के लिए ही कथन शामिल है (यह मानकीकरण प्रमेय है)। इसके विपरीत, लागू आदेश में कमी समाप्त नहीं हो सकती है, भले ही शब्द का सामान्य रूप हो। उदाहरण के लिए, एप्लिकेटिव ऑर्डर कटौती का उपयोग करते हुए, कटौती का निम्नलिखित क्रम संभव है:
लेकिन सामान्य क्रम में कमी का उपयोग करते हुए, वही प्रारंभिक बिंदु जल्दी से सामान्य रूप में कम हो जाता है:
सिनोट के निर्देशक स्ट्रिंग ्स ऐसी विधि है जिसके द्वारा बीटा कमी की कम्प्यूटेशनल जटिलता को अनुकूलित किया जा सकता है।
यह भी देखें
- लैम्ब्डा कैलकुलस
- सामान्य रूप (बहुविकल्पी)
संदर्भ
- ↑ "बीटा सामान्य रूप". Encyclopedia. TheFreeDictionary.com. Retrieved 18 November 2013.
- ↑ Thompson, Simon (1991). प्रकार सिद्धांत और कार्यात्मक प्रोग्रामिंग. Wokingham, England: Addison-Wesley. p. 38. ISBN 0-201-41667-0. OCLC 23287456.
- ↑ 3.0 3.1 Barendregt, Henk P. (1984). लैम्ब्डा कैलकुलस का परिचय (PDF) (Revised ed.). p. 24.
- ↑ Thompson, Simon (1991). प्रकार सिद्धांत और कार्यात्मक प्रोग्रामिंग. Wokingham, England: Addison-Wesley. p. 35. ISBN 0-201-41667-0. OCLC 23287456.
- ↑ 5.0 5.1 5.2 Thompson, Simon (1991). प्रकार सिद्धांत और कार्यात्मक प्रोग्रामिंग. Wokingham, England: Addison-Wesley. p. 36. ISBN 0-201-41667-0. OCLC 23287456.
- ↑ "कमजोर सिर सामान्य रूप". Encyclopedia. TheFreeDictionary.com. Retrieved 30 April 2021.
