बीटा सामान्य रूप: Difference between revisions
No edit summary |
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 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> चूंकि इस शब्द से अधिक शीर्ष सामान्य रूप हो सकते हैं। | ||
==बीटा कमी== | ==बीटा कमी== | ||
| Line 5: | Line 5: | ||
:<math> (\mathbf{\lambda} x . A) M</math>. | :<math> (\mathbf{\lambda} x . A) M</math>. | ||
एक रेडेक्स <math>r</math> पद में शीर्ष स्थान पर है <math>t</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> \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> \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 | ||
\lambda x_1 \ldots \lambda x_n . A[x := M_1] M_2 \ldots M_m </math>, | \lambda x_1 \ldots \lambda x_n . A[x := M_1] M_2 \ldots M_m </math>, जहाँ <math>n \geq 0</math> और <math>m \geq 1</math>. | ||
कोई भी अन्य कमी आंतरिक बीटा कमी है। | कोई भी अन्य कमी आंतरिक बीटा कमी है। | ||
'सामान्य रूप' ऐसा शब्द है जिसमें कोई बीटा रेडेक्स नहीं होता है,<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> | 'सामान्य रूप' ऐसा शब्द है, जिसमें कोई बीटा रेडेक्स नहीं होता है,<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> \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>{{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>\begin{align} | :<math>\begin{align} | ||
| Line 44: | Line 44: | ||
&\ldots | &\ldots | ||
\end{align}</math> | \end{align}</math> | ||
अपितु सामान्य क्रम में कमी का उपयोग करते हुए, वही प्रारंभिक बिंदु जल्दी से सामान्य रूप में कम हो जाता है: | |||
:<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 16:18, 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.
