कप्पा कैलकुलस: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Tag: Manual revert
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[गणितीय तर्क]], [[श्रेणी सिद्धांत]], और में
[[गणितीय तर्क]] और [[श्रेणी सिद्धांत]] मुख्य रूप से [[कंप्यूटर विज्ञान]] में '''कप्पा कैलकुलस''' है, इसका प्रथम क्रम इसके कार्यों को परिभाषित करने के लिए [[औपचारिक प्रणाली]] या प्रथम-क्रम [[फ़ंक्शन (गणित)]] को व्यक्त करता हैं।
[[कंप्यूटर विज्ञान]], कप्पा कैलकुलस है
प्रथम क्रम कार्यों को परिभाषित करने के लिए [[औपचारिक प्रणाली]]|प्रथम-क्रम
[[फ़ंक्शन (गणित)]]


[[लैम्ब्डा कैलकुलस]] के विपरीत, कप्पा कैलकुलस में कोई नहीं है, उच्च-क्रम के कार्य; इसके कार्य हैं
[[लैम्ब्डा कैलकुलस]] के विपरीत, कप्पा कैलकुलस में कोई नहीं है, जिसके लिए उच्च-क्रम के कार्य द्वारा इसे प्रदर्शित करते हैं। इसके निम्नलिखित कार्य हैं, [[प्रथम श्रेणी की वस्तु]] नहीं रहती है, जिसके आधार पर यह कप्पा-कैलकुलस हो सकता है, टाइप किए गए प्रथम-क्रम के टुकड़े के पुनर्रचना के रूप में माना जाता है, जो लैम्ब्डा कैलकुलस को व्यक्त करता हैं।<ref name="Hasegawa"/>
[[प्रथम श्रेणी की वस्तु]] नहीं. कप्पा-कैलकुलस हो सकता है
टाइप किए गए प्रथम-क्रम के टुकड़े के पुनर्रचना के रूप में माना जाता है
लैम्ब्डा कैलकुलस।<ref name="Hasegawa"/>


क्योंकि इसके कार्य प्रथम श्रेणी की वस्तुएं नहीं हैं, कप्पा का मूल्यांकन
क्योंकि इसके कार्य प्रथम श्रेणी की वस्तुएं नहीं हैं, कप्पा का मूल्यांकन कैलकुलस मुख्य रूप से अभिव्यक्ति की आवश्यकता नहीं है, जो [[समापन (कंप्यूटर विज्ञान)]] को व्यक्त करता हैं।
कैलकुलस अभिव्यक्ति की आवश्यकता नहीं है
[[समापन (कंप्यूटर विज्ञान)]]


== परिभाषा ==
== परिभाषा ==


नीचे दी गई परिभाषा हसेगावा के पृष्ठ 205 और 207 पर दिए गए चित्र से ली गई है।<ref name="Hasegawa"/>
नीचे दी गई परिभाषा हसेगावा के पृष्ठ 205 और 207 पर दिए गए चित्र से ली गई है।<ref name="Hasegawa"/>
=== व्याकरण ===
=== व्याकरण ===


कप्पा कैलकुलस में दिए गए प्रकार और अभिव्यक्तियाँ शामिल हैं
कप्पा कैलकुलस में दिए गए प्रकार और अभिव्यक्तियाँ उपस्थित हैं, नीचे व्याकरण:
नीचे व्याकरण:


:<math>
:<math>
Line 42: Line 30:


*1 प्रकार है
*1 प्रकार है
* अगर <math>\tau_1</math> और <math>\tau_2</math> तो प्रकार हैं <math>\tau_1\times\tau_2</math> प्रकार है.
* यदि <math>\tau_1</math> और <math>\tau_2</math> तो प्रकार हैं, तो <math>\tau_1\times\tau_2</math> इसका प्रकार है।
* प्रत्येक चर अभिव्यक्ति है
* प्रत्येक वैरियेबल एक अभिव्यक्ति है।
* अगर {{mvar|&tau;}} तो प्रकार है <math>id_\tau</math> अभिव्यक्ति है
* यदि {{mvar|&tau;}} तो प्रकार है, तथा <math>id_\tau</math> अभिव्यक्ति ।है
* अगर {{mvar|&tau;}} तो प्रकार है <math>!_\tau</math> अभिव्यक्ति है
* यदि {{mvar|&tau;}} तो प्रकार है, तथा <math>!_\tau</math> अभिव्यक्ति है।
* अगर {{mvar|&tau;}} प्रकार है और e अभिव्यक्ति है <math>\operatorname{lift}_\tau(e)</math> अभिव्यक्ति है
* यदि {{mvar|&tau;}} प्रकार है और e अभिव्यक्ति है, तथा <math>\operatorname{lift}_\tau(e)</math> अभिव्यक्ति है।
* अगर <math>e_1</math> और <math>e_2</math> तो फिर अभिव्यक्ति हैं <math>e_1\circ e_2</math> अभिव्यक्ति है
* यदि <math>e_1</math> और <math>e_2</math> तो फिर अभिव्यक्ति हैं, तथा <math>e_1\circ e_2</math> अभिव्यक्ति है।
* यदि x चर है, {{mvar|&tau;}} प्रकार है, और e अभिव्यक्ति है <math>\kappa x{:}1{\to}\tau\;.\;e</math> अभिव्यक्ति है <math>:1{\to}\tau</math> h> और की सबस्क्रिप्ट {{math|id}}, {{math|!}}, और <math>\operatorname{lift}</math> हैं
* यदि x चर है, {{mvar|&tau;}} प्रकार है, और e अभिव्यक्ति है, तथा <math>\kappa x{:}1{\to}\tau\;.\;e</math> अभिव्यक्ति है <math>:1{\to}\tau</math> h> और की सबस्क्रिप्ट {{math|id}}, {{math|!}}, और <math>\operatorname{lift}</math> हैं।
कभी-कभी छोड़ दिया जाता है जब उन्हें स्पष्ट रूप से निर्धारित किया जा सकता है
कभी-कभी छोड़ दिया जाता है जब उन्हें स्पष्ट रूप से इसके प्रसंग द्वारा निर्धारित किया जा सकता है।
प्रसंग।


Juxtaposition का प्रयोग अक्सर संयोजन के संक्षिप्त रूप के रूप में किया जाता है
जक्स्टापोजीशन का प्रयोग अधिकांशतः  <math>\operatorname{lift}</math> और रचना के संयोजन के संक्षिप्त रूप के रूप में किया जाता है,:
<math>\operatorname{lift}</math> और रचना:


:<math>
:<math>
e_1 e_2\ \overset\operatorname{def}{=}\ e_1 \circ \operatorname{lift}(e_2)
e_1 e_2\ \overset\operatorname{def}{=}\ e_1 \circ \operatorname{lift}(e_2)
</math>
</math>
=== टाइपिंग नियम ===
=== टाइपिंग नियम ===


यहां प्रस्तुतीकरण अनुक्रमों का उपयोग करता है (<math>\Gamma\vdash e:\tau</math>) केवल टाइप किए गए लैम्ब्डा कैलकुलस के साथ तुलना को आसान बनाने के लिए काल्पनिक निर्णयों के बजाय। इसके लिए अतिरिक्त वार नियम की आवश्यकता है, जो हसेगावा में प्रकट नहीं होता है<ref name="Hasegawa"/>
यहां प्रस्तुतीकरण अनुक्रमों (<math>\Gamma\vdash e:\tau</math>) का उपयोग करता है, जो केवल टाइप किए गए लैम्ब्डा कैलकुलस के साथ तुलना को साधारण बनाने के लिए काल्पनिक निर्णयों के अतिरिक्त उपयोगी हैं। इसके लिए अतिरिक्त वार नियम की आवश्यकता है, जो हसेगावा में प्रकट नहीं होता है<ref name="Hasegawa"/>


कप्पा कैलकुलस में अभिव्यक्ति के दो प्रकार होते हैं: उसके स्रोत का प्रकार और उसके लक्ष्य का प्रकार। संकेतन <math>e:\tau_1{\to}\tau_2</math> यह इंगित करने के लिए प्रयोग किया जाता है कि अभिव्यक्ति ई में स्रोत प्रकार है <math>{\tau_1}</math> और लक्ष्य प्रकार <math>{\tau_2}</math>.
कप्पा कैलकुलस में अभिव्यक्ति के दो प्रकार होते हैं: उसके स्रोत का प्रकार और यह इसके लक्ष्य का प्रकार हैं। इसका संकेतन <math>e:\tau_1{\to}\tau_2</math> द्वारा किया जाता हैं, जिसका यह इंगित करने के लिए प्रयोग किया जाता है कि अभिव्यक्ति ई में <math>{\tau_1}</math> और लक्ष्य प्रकार <math>{\tau_2}</math> स्रोत प्रकार है।


कप्पा कैलकुलस में अभिव्यक्तियों को निम्नलिखित नियमों के अनुसार प्रकार निर्दिष्ट किया गया है:
कप्पा कैलकुलस में अभिव्यक्तियों को निम्नलिखित नियमों के अनुसार प्रकार निर्दिष्ट किया गया है:
Line 94: Line 78:
दूसरे शब्दों में,
दूसरे शब्दों में,


* वर: मान लेना <math>x:1{\to}\tau</math> आपको यह निष्कर्ष निकालने देता है <math>x:1{\to}\tau</math>
* वीएआर: मान लेना <math>x:1{\to}\tau</math> आपको <math>x:1{\to}\tau</math> निष्कर्ष निकालने देता है।
* आईडी: किसी भी प्रकार के लिए {{mvar|&tau;}}, <math>id_\tau:\tau{\to}\tau</math>
* आईडी: किसी भी प्रकार के लिए {{mvar|&tau;}}, <math>id_\tau:\tau{\to}\tau</math> का उपयोग करता हैं।
* बैंग: किसी भी प्रकार के लिए {{mvar|&tau;}}, <math>!_\tau:\tau{\to}1</math>
* बैंग: किसी भी प्रकार के लिए {{mvar|&tau;}}, <math>!_\tau:\tau{\to}1</math> का उपयोग करता हैं।
* Comp: यदि लक्ष्य प्रकार का <math>e_1</math> के स्रोत प्रकार से मेल खाता है <math>e_2</math> उन्हें अभिव्यक्ति बनाने के लिए रचा जा सकता है <math>e_2\circ e_1</math> स्रोत प्रकार के साथ <math>e_1</math> और लक्ष्य प्रकार <math>e_2</math>
* कंप: यदि लक्ष्य प्रकार का <math>e_1</math> के स्रोत प्रकार से मेल खाता है <math>e_2</math> उन्हें अभिव्यक्ति बनाने के लिए रचा जा सकता है, <math>e_2\circ e_1</math> स्रोत प्रकार के साथ <math>e_1</math> और लक्ष्य प्रकार <math>e_2</math> प्रकार का हैं।
* लिफ्ट: यदि <math>e:1{\to}\tau_1</math>, तब <math>\operatorname{lift}_{\tau_2}(e):\tau_2{\to}(\tau_1\times\tau_2)</math>
* लिफ्ट: यदि <math>e:1{\to}\tau_1</math>, तब <math>\operatorname{lift}_{\tau_2}(e):\tau_2{\to}(\tau_1\times\tau_2)</math> प्राप्त होता हैं।
* कप्पा: यदि हम यह निष्कर्ष निकाल सकें <math>e:\tau_2\to\tau_3</math> इस धारणा के तहत <math>x:1{\to}\tau_1</math>, तो हम इस धारणा के बिना निष्कर्ष निकाल सकते हैं कि <math>\kappa x{:}1{\to}\tau_1\,.\,e\;:\;\tau_1\times\tau_2\to\tau_3</math>
* कप्पा: यदि हम <math>e:\tau_2\to\tau_3</math> निष्कर्ष निकाल सकें, इस धारणा के अनुसार <math>x:1{\to}\tau_1</math> को हम इस धारणा के बिना निष्कर्ष निकाल सकते हैं कि <math>\kappa x{:}1{\to}\tau_1\,.\,e\;:\;\tau_1\times\tau_2\to\tau_3</math> प्राप्त हो।
 
 
=== समानताएँ ===
=== समानताएँ ===


कप्पा कैलकुलस निम्नलिखित समानताओं का पालन करता है:
कप्पा कैलकुलस निम्नलिखित समानताओं का पालन करता है:


*तटस्थता: यदि <math>f:\tau_1{\to}\tau_2</math> तब <math>f{\circ}id_{\tau_1}=f</math> और <math>f=id_{\tau_2}{\circ}f</math>
*तटस्थता: यदि <math>f:\tau_1{\to}\tau_2</math> तब <math>f{\circ}id_{\tau_1}=f</math> और <math>f=id_{\tau_2}{\circ}f</math> हैं।
*सहयोगिता: यदि <math>f:\tau_1{\to}\tau_2</math>, <math>g:\tau_2{\to}\tau_3</math>, और <math>h:\tau_3{\to}\tau_4</math>, तब <math>(h{\circ}g){\circ}f = h{\circ}(g{\circ}f)</math>.
*सहयोगिता: यदि <math>f:\tau_1{\to}\tau_2</math>, <math>g:\tau_2{\to}\tau_3</math>, और <math>h:\tau_3{\to}\tau_4</math>, तब <math>(h{\circ}g){\circ}f = h{\circ}(g{\circ}f)</math> हैं।
* टर्मिनललिटी: यदि <math>f{:}\tau{\to}1</math> और <math>g{:}\tau{\to}1</math> तब <math>f=g</math>
* टर्मिनललिटी: यदि <math>f{:}\tau{\to}1</math> और <math>g{:}\tau{\to}1</math> तब <math>f=g</math> हैं।
* लिफ्ट-कमी: <math>(\kappa x.f)\circ \operatorname{lift}_\tau(c) = f[c/x]</math>
* लिफ्ट-कमी: <math>(\kappa x.f)\circ \operatorname{lift}_\tau(c) = f[c/x]</math> हैं।
* कप्पा-कमी: <math>\kappa x. (h\circ \operatorname{lift}_\tau(x)) = h</math> यदि x, h में मुफ़्त नहीं है
* कप्पा-कमी: <math>\kappa x. (h\circ \operatorname{lift}_\tau(x)) = h</math> यदि x, h में मुफ़्त नहीं है।


अंतिम दो समानताएं कलन के लिए कटौती नियम हैं,
अंतिम दो समानताएं कलन के लिए कटौती नियम हैं, जिसे बाएँ से दाएँ पुनः लिखा जाता हैं।।
बाएँ से दाएँ पुनः लिखना।


== गुण ==
== गुण ==


प्ररूप {{val|1}} को [[इकाई प्रकार]] माना जा सकता है। इसके कारण, कोई भी दो फ़ंक्शन जिनका तर्क प्रकार समान है और जिनका परिणाम प्रकार समान है {{val|1}} बराबर होना चाहिए - क्योंकि प्रकार का केवल ही मान है {{val|1}} दोनों फ़ंक्शन को प्रत्येक तर्क (टर्मिनैलिटी) के लिए वह मान लौटाना होगा।
प्रारूप {{val|1}} को [[इकाई प्रकार]] माना जा सकता है। इसके कारण, कोई भी दो फ़ंक्शन जिनका तर्क प्रकार समान है और जिनका परिणाम प्रकार समान है, वे {{val|1}} के बराबर होने चाहिए- क्योंकि प्रकार का केवल ही मान है, इस प्रकार {{val|1}} दोनों फ़ंक्शन को प्रत्येक तर्क (टर्मिनैलिटी) के लिए वह मान लौटाना होगा।


प्रकार सहित भाव <math>1{\to}\tau</math> जमीन के प्रकार के स्थिरांक या मान के रूप में माना जा सकता है; यह है क्योंकि {{val|1}} इकाई प्रकार है, और इसलिए इस प्रकार का फ़ंक्शन आवश्यक रूप से स्थिर फ़ंक्शन है। ध्यान दें कि कप्पा नियम केवल अमूर्तता की अनुमति देता है जब अमूर्त किए जा रहे चर का प्रकार होता है <math>1{\to}\tau</math> कुछ के लिए {{mvar|&tau;}}. यह बुनियादी तंत्र है जो यह सुनिश्चित करता है कि सभी कार्य प्रथम-क्रम के हों।
इस प्रकार इसके सहित <math>1{\to}\tau</math> भाव को इसके आधार के स्थिरांक या मान के रूप में माना जा सकता है, जो यह है क्योंकि {{val|1}} इकाई प्रकार का है, और इसलिए इस प्रकार का फ़ंक्शन आवश्यक रूप से स्थिर फ़ंक्शन है। ध्यान दें कि कप्पा नियम केवल अमूर्तता की अनुमति देता है, जब अमूर्त किए जा रहे वैरियेबल का प्रकार <math>1{\to}\tau</math> होता है, तब कुछ {{mvar|&tau;}} के लिए यह मौलिक तंत्र है, जो यह सुनिश्चित करता है कि सभी कार्य प्रथम-क्रम के हों।


== श्रेणीबद्ध शब्दार्थ ==
== श्रेणीबद्ध शब्दार्थ ==


कप्पा कैलकुलस की आंतरिक भाषा होने का इरादा है
कप्पा कैलकुलस की आंतरिक भाषा होने का चिह्न है, इसके प्रासंगिक रूप से पूर्ण श्रेणियाँ प्राप्त होती हैं।
प्रासंगिक रूप से पूर्ण श्रेणियाँ।


== उदाहरण ==
== उदाहरण ==


अनेक तर्कों वाले भावों के स्रोत प्रकार होते हैं जो हैं
अनेक तर्कों वाले भावों के स्रोत प्रकार होते हैं जो हैं, जिसके लिए दाएँ-असंतुलित बाइनरी ट्री को उदाहरण के लिए तीन f फ़ंक्शन प्रकार के ए, बी, और सी के तर्क और परिणाम प्रकार डी में प्रकार होगा जो इस प्रकार हैं।
दाएँ-असंतुलित बाइनरी पेड़। उदाहरण के लिए, तीन वाला फ़ंक्शन f
प्रकार ए, बी, और सी के तर्क और परिणाम प्रकार डी में प्रकार होगा
 
: <math>
: <math>
   f : A\times (B\times (C\times 1)) \to D
   f : A\times (B\times (C\times 1)) \to D
</math>
</math>
यदि हम वाम-सहयोगी जुड़ाव को परिभाषित करते हैं <math>f\;c</math> संक्षिप्त रूप में
यदि हम वाम-सहयोगी जुड़ाव को <math>f\;c</math> संक्षिप्त रूप में परिभाषित करते हैं, जिसके लिए <math>(f\circ \operatorname{lift}(c))</math>, फिर <math>a:1{\to}A</math>, <math>b:1{\to}B</math> को मानकर और <math>c:1{\to}C</math> को हम इस फ़ंक्शन को लागू कर सकते हैं:
के लिए <math>(f\circ \operatorname{lift}(c))</math>, फिर - ऐसा मानकर
<math>a:1{\to}A</math>, <math>b:1{\to}B</math>, और
<math>c:1{\to}C</math> - हम इस फ़ंक्शन को लागू कर सकते हैं:


: <math>
: <math>
   f\;a\;b\;c\;:\;1 \to D
   f\;a\;b\;c\;:\;1 \to D
</math>
</math>
अभिव्यक्ति के बाद से <math>f\;a\;b\;c</math> स्रोत प्रकार है {{val|1}}, यह ग्राउंड वैल्यू है और इसे किसी अन्य फ़ंक्शन के तर्क के रूप में पारित किया जा सकता है। अगर <math>g:(D\times E){\to}F</math>, तब
अभिव्यक्ति के बाद से <math>f\;a\;b\;c</math> स्रोत प्रकार है {{val|1}}, यह ग्राउंड वैल्यू है और इसे किसी अन्य फ़ंक्शन के तर्क के रूप में पारित किया जा सकता है। यदि <math>g:(D\times E){\to}F</math>, तब


: <math>
: <math>
   g\;(f\;a\;b\;c)\;:\;E \to F
   g\;(f\;a\;b\;c)\;:\;E \to F
</math>
</math>
काफी हद तक तयशुदा प्रकार के फ़ंक्शन की तरह
इस सीमा तक प्राप्त होने वाले इन प्रकारों के फ़ंक्शन <math>A{\to}(B{\to}(C{\to}D))</math> के समान लैम्ब्डा कैलकुलस में, आंशिक आवेदन संभव है:
<math>A{\to}(B{\to}(C{\to}D))</math> लैम्ब्डा कैलकुलस में, आंशिक
आवेदन संभव है:


: <math>
: <math>
   f\;a\;:\;B\times (C\times 1) \to D
   f\;a\;:\;B\times (C\times 1) \to D
</math>
</math>
हालाँकि कोई उच्चतर प्रकार नहीं (अर्थात्) <math>(\tau{\to}\tau){\to}\tau</math>) वह शामिल। ध्यान दें क्योंकि स्रोत प्रकार का {{mvar|f a}} क्या नहीं है {{val|1}}, अब तक उल्लिखित मान्यताओं के तहत निम्नलिखित अभिव्यक्ति को अच्छी तरह से टाइप नहीं किया जा सकता है:
चूंकि इसका कोई उच्चतर प्रकार नहीं हैं, अर्थात <math>(\tau{\to}\tau){\to}\tau</math>) इसमें उपस्थित हैं। ध्यान दें क्योंकि स्रोत प्रकार का {{mvar|f a}} क्या {{val|1}} नहीं है, अब तक उल्लिखित मान्यताओं के तहत निम्नलिखित अभिव्यक्ति को अच्छी तरह से टाइप नहीं किया जा सकता है:


: <math>
: <math>
Line 161: Line 133:
</math>
</math>
क्योंकि क्रमिक अनुप्रयोग का उपयोग एकाधिक के लिए किया जाता है
क्योंकि क्रमिक अनुप्रयोग का उपयोग एकाधिक के लिए किया जाता है
तर्कों में किसी फ़ंक्शन की योग्यता जानना आवश्यक नहीं है
तर्कों में किसी फ़ंक्शन की योग्यता जानना आवश्यक नहीं है, इसकी टाइपिंग निर्धारित करने का आदेश उदाहरण के लिए, यदि हम यह जानते हैं<math>c:1{\to}C</math> फिर यह अभिव्यक्ति इस प्रकार हैं-
इसकी टाइपिंग निर्धारित करने का आदेश; उदाहरण के लिए, यदि हम यह जानते हैं
<math>c:1{\to}C</math> फिर अभिव्यक्ति


: {{mvar| j c }}
: {{mvar| j c }}


जब तक यह अच्छी तरह से टाइप किया गया है {{mvar|j}} प्रकार है
जब तक यह अच्छी तरह से टाइप किया गया है, जिसे {{mvar|j}} प्रकार से इंगित करते हैं।
: <math>(C\times\alpha){\to}\beta</math> कुछ के लिए {{mvar|&alpha;}}
: <math>(C\times\alpha){\to}\beta</math> कुछ के लिए {{mvar|&alpha;}}
और {{mvar|&beta;}}. गणना करते समय यह संपत्ति महत्वपूर्ण है
और {{mvar|&beta;}} की गणना करते समय यह संपत्ति महत्वपूर्ण है, इसकी अभिव्यक्ति का मुख्य प्रकार जो उच्च-क्रम को बाहर करने का प्रयास करते समय कठिन हो सकता है, इनके प्रकारों के व्याकरण को सीमित करके टाइप किए गए लैम्ब्डा कैलकुली से कार्य करता है।
अभिव्यक्ति का मुख्य प्रकार, कुछ
जो उच्च-क्रम को बाहर करने का प्रयास करते समय कठिन हो सकता है
प्रकारों के व्याकरण को सीमित करके टाइप किए गए लैम्ब्डा कैलकुली से कार्य करता है।


== इतिहास ==
== इतिहास ==


बेरेन्ड्रेट ने मूल रूप से परिचय दिया<ref name="Barendregt"/>शब्द
बेरेन्ड्रेट ने मूल रूप से परिचय दिया गया हैं।<ref name="Barendregt"/>
  संयोजन बीजगणित के संदर्भ में कार्यात्मक पूर्णता।
  संयोजन बीजगणित के संदर्भ में कार्यात्मक पूर्णता
कप्पा कैलकुलस लैम्बेक<ref के प्रयासों से उत्पन्न हुआ
कप्पा कैलकुलस लैम्बेक<ref के प्रयासों से उत्पन्न हुआ
नाम = लाम्बेक /> कार्यात्मक का उपयुक्त एनालॉग तैयार करने के लिए
<ref name= Lambek/> कार्यात्मक का उपयुक्त एनालॉग तैयार करने के लिए इस श्रेणियों के लिए पूर्णता द्वारा प्रतिपादित किया जाता हैं।<ref>हर्मिडा और जैकब्स देखें</ref> हसेगावा ने बाद में कप्पा विकसित किया गया हैं। इस कैलकुलस को प्रयोग करने योग्य यद्यपि सरल प्रोग्रामिंग भाषा में उपस्थित करते हैं, इसकी प्राकृतिक संख्याओं और पुनरावृत्ति पर अंकगणित को व्यक्त करते हैं। <ref>हसेगावा</ref> एरो से कनेक्शन के लिए कंप्यूटर विज्ञान में जांच की गई<ref name="closed"/> पावर, थिएलेके और अन्य लोगो द्वारा की गई थी।(see Hermida and Jacobs,<ref
मनमानी श्रेणियों के लिए पूर्णता (हर्मिडा और जैकब्स देखें,<रेफरी)।
name=HermidaJacobs/> section 1)
नाम=हर्मिडा जैकब्स/> अनुभाग 1)। हसेगावा ने बाद में कप्पा विकसित किया
 
कैलकुलस को प्रयोग करने योग्य (यद्यपि सरल) प्रोग्रामिंग भाषा में शामिल करें
 
प्राकृतिक संख्याओं और आदिम पुनरावृत्ति पर अंकगणित।<रेफरी
 
नाम = हसेगावा /> एरो से कनेक्शन (कंप्यूटर विज्ञान)
 
बाद में जांच की गई<ref name="closed"/>पावर, थिएलेके और अन्य द्वारा।
 
 


== वेरिएंट ==
== वेरिएंट ==


कप्पा कैलकुलस के संस्करणों का पता लगाना संभव है
कप्पा कैलकुलस के संस्करणों का पता लगाना संभव है, इस प्रकार [[अवसंरचनात्मक तर्क]] जैसे [[रैखिक प्रकार प्रणाली]], [[एफ़िन तर्क]] और गैरअनुवांशिक तर्क प्रकार के हैं। इन एक्सटेंशन को हटाने की आवश्यकता है, जिसे प्रतिबंधित करना <math>!_\tau</math> की अभिव्यक्ति हैं। ऐसी परिस्थितियों में {{math|&times;}} प्रकार के ऑपरेटर के लिए यह सत्य कार्टेशियन उत्पाद नहीं है, और इसे सामान्यत रूप से {{math|&otimes;}} द्वारा लिखा जाता है।
[[अवसंरचनात्मक तर्क]] जैसे [[रैखिक प्रकार प्रणाली]], [[एफ़िन तर्क]],
और गैरअनुवांशिक तर्क प्रकार। इन एक्सटेंशनों को हटाने की आवश्यकता है या
को प्रतिबंधित करना <math>!_\tau</math> अभिव्यक्ति। ऐसी परिस्थितियों में
{{math|&times;}} प्रकार ऑपरेटर सच्चा कार्टेशियन उत्पाद नहीं है,
और आम तौर पर लिखा जाता है {{math|&otimes;}} इसे स्पष्ट करने के लिए।
 
== संदर्भ ==
== संदर्भ ==


Line 297: Line 259:
</ref>
</ref>
</references>
</references>
[[Category: तार्किक गणना]]


[[Category: Machine Translated Page]]
[[Category:Created On 08/07/2023]]
[[Category:Created On 08/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with reference errors]]
[[Category:Templates Vigyan Ready]]
[[Category:तार्किक गणना]]

Latest revision as of 19:10, 21 July 2023

गणितीय तर्क और श्रेणी सिद्धांत मुख्य रूप से कंप्यूटर विज्ञान में कप्पा कैलकुलस है, इसका प्रथम क्रम इसके कार्यों को परिभाषित करने के लिए औपचारिक प्रणाली या प्रथम-क्रम फ़ंक्शन (गणित) को व्यक्त करता हैं।

लैम्ब्डा कैलकुलस के विपरीत, कप्पा कैलकुलस में कोई नहीं है, जिसके लिए उच्च-क्रम के कार्य द्वारा इसे प्रदर्शित करते हैं। इसके निम्नलिखित कार्य हैं, प्रथम श्रेणी की वस्तु नहीं रहती है, जिसके आधार पर यह कप्पा-कैलकुलस हो सकता है, टाइप किए गए प्रथम-क्रम के टुकड़े के पुनर्रचना के रूप में माना जाता है, जो लैम्ब्डा कैलकुलस को व्यक्त करता हैं।[1]

क्योंकि इसके कार्य प्रथम श्रेणी की वस्तुएं नहीं हैं, कप्पा का मूल्यांकन कैलकुलस मुख्य रूप से अभिव्यक्ति की आवश्यकता नहीं है, जो समापन (कंप्यूटर विज्ञान) को व्यक्त करता हैं।

परिभाषा

नीचे दी गई परिभाषा हसेगावा के पृष्ठ 205 और 207 पर दिए गए चित्र से ली गई है।[1]

व्याकरण

कप्पा कैलकुलस में दिए गए प्रकार और अभिव्यक्तियाँ उपस्थित हैं, नीचे व्याकरण:

दूसरे शब्दों में,

  • 1 प्रकार है
  • यदि और तो प्रकार हैं, तो इसका प्रकार है।
  • प्रत्येक वैरियेबल एक अभिव्यक्ति है।
  • यदि τ तो प्रकार है, तथा अभिव्यक्ति ।है
  • यदि τ तो प्रकार है, तथा अभिव्यक्ति है।
  • यदि τ प्रकार है और e अभिव्यक्ति है, तथा अभिव्यक्ति है।
  • यदि और तो फिर अभिव्यक्ति हैं, तथा अभिव्यक्ति है।
  • यदि x चर है, τ प्रकार है, और e अभिव्यक्ति है, तथा अभिव्यक्ति है h> और की सबस्क्रिप्ट id, !, और हैं।

कभी-कभी छोड़ दिया जाता है जब उन्हें स्पष्ट रूप से इसके प्रसंग द्वारा निर्धारित किया जा सकता है।

जक्स्टापोजीशन का प्रयोग अधिकांशतः और रचना के संयोजन के संक्षिप्त रूप के रूप में किया जाता है,:

टाइपिंग नियम

यहां प्रस्तुतीकरण अनुक्रमों () का उपयोग करता है, जो केवल टाइप किए गए लैम्ब्डा कैलकुलस के साथ तुलना को साधारण बनाने के लिए काल्पनिक निर्णयों के अतिरिक्त उपयोगी हैं। इसके लिए अतिरिक्त वार नियम की आवश्यकता है, जो हसेगावा में प्रकट नहीं होता है[1]

कप्पा कैलकुलस में अभिव्यक्ति के दो प्रकार होते हैं: उसके स्रोत का प्रकार और यह इसके लक्ष्य का प्रकार हैं। इसका संकेतन द्वारा किया जाता हैं, जिसका यह इंगित करने के लिए प्रयोग किया जाता है कि अभिव्यक्ति ई में और लक्ष्य प्रकार स्रोत प्रकार है।

कप्पा कैलकुलस में अभिव्यक्तियों को निम्नलिखित नियमों के अनुसार प्रकार निर्दिष्ट किया गया है:

(Var)
(Id)
(Bang)
(Comp)
(Lift)
(Kappa)

दूसरे शब्दों में,

  • वीएआर: मान लेना आपको निष्कर्ष निकालने देता है।
  • आईडी: किसी भी प्रकार के लिए τ, का उपयोग करता हैं।
  • बैंग: किसी भी प्रकार के लिए τ, का उपयोग करता हैं।
  • कंप: यदि लक्ष्य प्रकार का के स्रोत प्रकार से मेल खाता है उन्हें अभिव्यक्ति बनाने के लिए रचा जा सकता है, स्रोत प्रकार के साथ और लक्ष्य प्रकार प्रकार का हैं।
  • लिफ्ट: यदि , तब प्राप्त होता हैं।
  • कप्पा: यदि हम निष्कर्ष निकाल सकें, इस धारणा के अनुसार को हम इस धारणा के बिना निष्कर्ष निकाल सकते हैं कि प्राप्त हो।

समानताएँ

कप्पा कैलकुलस निम्नलिखित समानताओं का पालन करता है:

  • तटस्थता: यदि तब और हैं।
  • सहयोगिता: यदि , , और , तब हैं।
  • टर्मिनललिटी: यदि और तब हैं।
  • लिफ्ट-कमी: हैं।
  • कप्पा-कमी: यदि x, h में मुफ़्त नहीं है।

अंतिम दो समानताएं कलन के लिए कटौती नियम हैं, जिसे बाएँ से दाएँ पुनः लिखा जाता हैं।।

गुण

प्रारूप 1 को इकाई प्रकार माना जा सकता है। इसके कारण, कोई भी दो फ़ंक्शन जिनका तर्क प्रकार समान है और जिनका परिणाम प्रकार समान है, वे 1 के बराबर होने चाहिए- क्योंकि प्रकार का केवल ही मान है, इस प्रकार 1 दोनों फ़ंक्शन को प्रत्येक तर्क (टर्मिनैलिटी) के लिए वह मान लौटाना होगा।

इस प्रकार इसके सहित भाव को इसके आधार के स्थिरांक या मान के रूप में माना जा सकता है, जो यह है क्योंकि 1 इकाई प्रकार का है, और इसलिए इस प्रकार का फ़ंक्शन आवश्यक रूप से स्थिर फ़ंक्शन है। ध्यान दें कि कप्पा नियम केवल अमूर्तता की अनुमति देता है, जब अमूर्त किए जा रहे वैरियेबल का प्रकार होता है, तब कुछ τ के लिए यह मौलिक तंत्र है, जो यह सुनिश्चित करता है कि सभी कार्य प्रथम-क्रम के हों।

श्रेणीबद्ध शब्दार्थ

कप्पा कैलकुलस की आंतरिक भाषा होने का चिह्न है, इसके प्रासंगिक रूप से पूर्ण श्रेणियाँ प्राप्त होती हैं।

उदाहरण

अनेक तर्कों वाले भावों के स्रोत प्रकार होते हैं जो हैं, जिसके लिए दाएँ-असंतुलित बाइनरी ट्री को उदाहरण के लिए तीन f फ़ंक्शन प्रकार के ए, बी, और सी के तर्क और परिणाम प्रकार डी में प्रकार होगा जो इस प्रकार हैं।

यदि हम वाम-सहयोगी जुड़ाव को संक्षिप्त रूप में परिभाषित करते हैं, जिसके लिए , फिर , को मानकर और को हम इस फ़ंक्शन को लागू कर सकते हैं:

अभिव्यक्ति के बाद से स्रोत प्रकार है 1, यह ग्राउंड वैल्यू है और इसे किसी अन्य फ़ंक्शन के तर्क के रूप में पारित किया जा सकता है। यदि , तब

इस सीमा तक प्राप्त होने वाले इन प्रकारों के फ़ंक्शन के समान लैम्ब्डा कैलकुलस में, आंशिक आवेदन संभव है:

चूंकि इसका कोई उच्चतर प्रकार नहीं हैं, अर्थात ) इसमें उपस्थित हैं। ध्यान दें क्योंकि स्रोत प्रकार का f a क्या 1 नहीं है, अब तक उल्लिखित मान्यताओं के तहत निम्नलिखित अभिव्यक्ति को अच्छी तरह से टाइप नहीं किया जा सकता है:

क्योंकि क्रमिक अनुप्रयोग का उपयोग एकाधिक के लिए किया जाता है तर्कों में किसी फ़ंक्शन की योग्यता जानना आवश्यक नहीं है, इसकी टाइपिंग निर्धारित करने का आदेश उदाहरण के लिए, यदि हम यह जानते हैं फिर यह अभिव्यक्ति इस प्रकार हैं-

j c

जब तक यह अच्छी तरह से टाइप किया गया है, जिसे j प्रकार से इंगित करते हैं।

कुछ के लिए α

और β की गणना करते समय यह संपत्ति महत्वपूर्ण है, इसकी अभिव्यक्ति का मुख्य प्रकार जो उच्च-क्रम को बाहर करने का प्रयास करते समय कठिन हो सकता है, इनके प्रकारों के व्याकरण को सीमित करके टाइप किए गए लैम्ब्डा कैलकुली से कार्य करता है।

इतिहास

बेरेन्ड्रेट ने मूल रूप से परिचय दिया गया हैं।[2]

संयोजन बीजगणित के संदर्भ में कार्यात्मक पूर्णता

कप्पा कैलकुलस लैम्बेक[3] कार्यात्मक का उपयुक्त एनालॉग तैयार करने के लिए इस श्रेणियों के लिए पूर्णता द्वारा प्रतिपादित किया जाता हैं।[4] हसेगावा ने बाद में कप्पा विकसित किया गया हैं। इस कैलकुलस को प्रयोग करने योग्य यद्यपि सरल प्रोग्रामिंग भाषा में उपस्थित करते हैं, इसकी प्राकृतिक संख्याओं और पुनरावृत्ति पर अंकगणित को व्यक्त करते हैं। [5] एरो से कनेक्शन के लिए कंप्यूटर विज्ञान में जांच की गई[6] पावर, थिएलेके और अन्य लोगो द्वारा की गई थी।(see Hermida and Jacobs,[7] section 1)




वेरिएंट

कप्पा कैलकुलस के संस्करणों का पता लगाना संभव है, इस प्रकार अवसंरचनात्मक तर्क जैसे रैखिक प्रकार प्रणाली, एफ़िन तर्क और गैरअनुवांशिक तर्क प्रकार के हैं। इन एक्सटेंशन को हटाने की आवश्यकता है, जिसे प्रतिबंधित करना की अभिव्यक्ति हैं। ऐसी परिस्थितियों में × प्रकार के ऑपरेटर के लिए यह सत्य कार्टेशियन उत्पाद नहीं है, और इसे सामान्यत रूप से द्वारा लिखा जाता है।

संदर्भ

  1. 1.0 1.1 1.2 Hasegawa, Masahito (1995). "Decomposing typed lambda calculus into a couple of categorical programming languages". In Pitt, David; Rydeheard, David E.; Johnstone, Peter (eds.). Category Theory and Computer Science. pp. 200–219. CiteSeerX 10.1.1.53.715. doi:10.1007/3-540-60164-3_28. ISBN 978-3-540-60164-7. ISSN 0302-9743. {{cite book}}: |journal= ignored (help)
  2. Barendregt, Hendrik Pieter, ed. (October 1, 1984). The Lambda Calculus: Its Syntax and Semantics. Studies in Logic and the Foundations of Mathematics. Vol. 103 (Revised ed.). Amsterdam, North Holland: Elsevier Science. ISBN 978-0-444-87508-2.
  3. Lambek, Joachim (August 1, 1973). "Functional completeness of cartesian categories". Annals of Mathematical Logic (published March 1974). 6 (3–4): 259–292. doi:10.1016/0003-4843(74)90003-5. ISSN 0003-4843.
  4. हर्मिडा और जैकब्स देखें
  5. हसेगावा
  6. Power, John; Thielecke, Hayo (1999). Wiedermann, Jiří; van Emde Boas, Peter; Nielsen, Mogens (eds.). Closed Freyd- and κ-Categories. pp. 625–634. CiteSeerX 10.1.1.42.2151. doi:10.1007/3-540-48523-6_59. ISBN 978-3-540-66224-2. ISSN 0302-9743. {{cite book}}: |journal= ignored (help)
  7. Hermida, Claudio; Jacobs, Bart (December 1995). "Fibrations with indeterminates: contextual and functional completeness for polymorphic lambda calculi". Mathematical Structures in Computer Science. 5 (4): 501–531. doi:10.1017/S0960129500001213. ISSN 1469-8072.