एसकेआई कॉम्बिनेटर कैलकुलस

एसकेआई कॉम्बिनेटर कैलकुलस एक संयोजन तर्क और गणना का एक मॉडल है। इसे एक कंप्यूटर प्रोग्रामिंग भाषा के रूप में सोचा जा सकता है, हालांकि यह सॉफ्टवेयर लिखने के लिए सुविधाजनक नहीं है। इसके बजाय, यह कलन विधि के गणितीय सिद्धांत में महत्वपूर्ण है क्योंकि यह एक अत्यंत सरल ट्यूरिंग पूर्ण भाषा है। इसकी तुलना अनटाइप्ड लैम्ब्डा कैलकुलस के संक्षिप्त संस्करण से की जा सकती है। इसे मोसेस शॉनफिंकेल द्वारा पेश किया गया था और हास्केल करी. लैम्ब्डा कैलकुलस में सभी ऑपरेशनों को कॉम्बिनेटरी लॉजिक#एस-के आधार की पूर्णता के माध्यम से एसकेआई कैलकुलस में द्विआधारी वृक्ष के रूप में एन्कोड किया जा सकता है, जिनकी पत्तियाँ तीन प्रतीकों एस, के, और आई (जिन्हें कॉम्बिनेटर कहा जाता है) में से एक हैं।

संकेतन

यद्यपि इस प्रणाली में वस्तुओं के सबसे औपचारिक प्रतिनिधित्व के लिए बाइनरी पेड़ों की आवश्यकता होती है, सरल टाइपसेटिंग के लिए उन्हें अक्सर कोष्ठक में अभिव्यक्ति के रूप में दर्शाया जाता है, जिस पेड़ का वे प्रतिनिधित्व करते हैं उसके लिए शॉर्टहैंड के रूप में। किसी भी उपवृक्ष को कोष्ठक में रखा जा सकता है, लेकिन अक्सर केवल दाहिनी ओर के उपवृक्ष को कोष्ठक में रखा जाता है, किसी भी अकोष्ठकीकृत अनुप्रयोगों के लिए बाईं ओर की संबद्धता निहित होती है। उदाहरण के लिए, ISK का अर्थ है ((IS)K)। इस नोटेशन का उपयोग करते हुए, एक पेड़ जिसका बायां उपवृक्ष पेड़ केएस है और जिसका दायां उपवृक्ष पेड़ एसके है, उसे केएस(एसके) के रूप में लिखा जा सकता है। यदि अधिक स्पष्टता वांछित है, तो निहित कोष्ठकों को भी शामिल किया जा सकता है: ((केएस)(एसके))।

अनौपचारिक विवरण

अनौपचारिक रूप से, और प्रोग्रामिंग भाषा शब्दजाल का उपयोग करते हुए, एक पेड़ (xy) को एक तर्क y पर लागू फ़ंक्शन x के रूप में सोचा जा सकता है। जब मूल्यांकन किया जाता है (यानी, जब फ़ंक्शन को तर्क पर लागू किया जाता है), तो पेड़ एक मान लौटाता है, यानी, दूसरे पेड़ में बदल जाता है। फ़ंक्शन, तर्क और मान या तो कॉम्बिनेटर या बाइनरी ट्री हैं। यदि वे द्विआधारी वृक्ष हैं, तो आवश्यकता पड़ने पर उन्हें फ़ंक्शन के रूप में भी सोचा जा सकता है।

'मूल्यांकन' ऑपरेशन को इस प्रकार परिभाषित किया गया है:

(x, y, और z 'S', 'K', और 'I' फ़ंक्शंस से बनी अभिव्यक्तियों का प्रतिनिधित्व करते हैं और मान निर्धारित करते हैं):

'मैं' अपना तर्क लौटाता है:

'आई'एक्स = एक्स

'K', जब किसी तर्क x पर लागू किया जाता है, तो एक-तर्क स्थिर फ़ंक्शन 'K'y प्राप्त होता है, जो किसी भी तर्क पर लागू होने पर, x लौटाता है:

'K'xy = x

'S' एक प्रतिस्थापन संचालिका है। यह तीन तर्क लेता है और फिर पहले तर्क को तीसरे पर लागू करता है, जिसे फिर तीसरे पर लागू दूसरे तर्क के परिणाम पर लागू किया जाता है। और स्पष्टता से:

'S'xyz = xz(yz)

उदाहरण गणना: 'एसकेएसके' 'एस'-नियम द्वारा 'केके'('एसके') का मूल्यांकन करता है। फिर यदि हम 'केके' ('एसके') का मूल्यांकन करते हैं, तो हमें 'के'-नियम से 'के' मिलता है। चूँकि कोई और नियम लागू नहीं किया जा सकता, गणना यहीं रुक जाती है।

सभी पेड़ों x और सभी पेड़ों y के लिए, 'SK'xy हमेशा दो चरणों में y का मूल्यांकन करेगा, 'K'y(xy) = y, इसलिए 'SK'xy के मूल्यांकन का अंतिम परिणाम हमेशा y के मूल्यांकन के परिणाम के बराबर होगा। . हम कहते हैं कि 'एसके'एक्स और 'आई' कार्यात्मक रूप से समतुल्य हैं क्योंकि किसी भी वाई पर लागू होने पर वे हमेशा एक ही परिणाम देते हैं।

इन परिभाषाओं से यह दिखाया जा सकता है कि एसकेआई कैलकुलस न्यूनतम प्रणाली नहीं है जो लैम्ब्डा कैलकुलस की गणना पूरी तरह से कर सकती है, क्योंकि किसी भी अभिव्यक्ति में 'आई' की सभी घटनाओं को ('एसकेके') या ('एसकेएस') द्वारा प्रतिस्थापित किया जा सकता है। या ('एसके' जो भी हो) और परिणामी अभिव्यक्ति समान परिणाम देगी। तो 'मैं' केवल वाक्यात्मक शर्करा है। चूँकि 'I' वैकल्पिक है, इसलिए सिस्टम को SK कैलकुलस या SK कॉम्बिनेटर कैलकुलस भी कहा जाता है।

केवल एक (अनुचित) कॉम्बिनेटर का उपयोग करके एक संपूर्ण सिस्टम को परिभाषित करना संभव है। एक उदाहरण क्रिस बार्कर का इओटा और जोट कॉम्बिनेटर है, जिसे 'एस' और 'के' के संदर्भ में निम्नानुसार व्यक्त किया जा सकता है:

ιx = x'SK'

आईओटा कॉम्बिनेटर से 'एस', 'के' और 'आई' का पुनर्निर्माण संभव है। ι को स्वयं पर लागू करने से ιι = ι'SK' = 'SSKK' = 'SK'('KK') प्राप्त होता है जो कार्यात्मक रूप से 'I' के समतुल्य है। 'K' का निर्माण 'I' में दो बार ι लगाने से किया जा सकता है (जो स्वयं पर ι लगाने के बराबर है): ι(ι(ιι)) = ι(ιι'SK') = ι('ISK') = ι ('एसके') = 'एसकेएसके' = 'के'। ι को एक बार और लगाने पर ι(ι(ι(ιι))) = ι'K' = 'KSK' = 'S' प्राप्त होता है।

औपचारिक परिभाषा

इस प्रणाली में शब्दों और व्युत्पत्तियों को अधिक औपचारिक रूप से परिभाषित किया जा सकता है:

शर्तें: पदों के समुच्चय T को निम्नलिखित नियमों द्वारा पुनरावर्ती रूप से परिभाषित किया गया है।

1. S, K, और I पद हैं।
2. यदि τ₁ और टी₂ पद हैं, तो (τ₁τ₂) एक शब्द है.
3. यदि पहले दो नियमों के अनुसार ऐसा होना आवश्यक न हो तो कोई भी चीज़ एक शब्द नहीं है।

व्युत्पत्तियाँ: व्युत्पत्ति निम्नलिखित नियमों द्वारा पुनरावर्ती रूप से परिभाषित शब्दों का एक सीमित अनुक्रम है (जहां α और ι वर्णमाला {S, K, I, (, )} पर शब्द हैं जबकि β, γ और δ शब्द हैं):

1. यदि Δ, α(Iβ)ι रूप की अभिव्यक्ति में समाप्त होने वाली व्युत्पत्ति है, तो Δ के बाद αβι शब्द एक व्युत्पत्ति है।
2. यदि Δ, α((Kβ)γ)ι रूप की अभिव्यक्ति में समाप्त होने वाली व्युत्पत्ति है, तो Δ के बाद αβι शब्द एक व्युत्पत्ति है।
3. यदि Δ, α(((Sβ)γ)δ)ι रूप की अभिव्यक्ति में समाप्त होने वाली व्युत्पत्ति है, तो Δ के बाद α((βδ)(γδ))ι शब्द एक व्युत्पत्ति है।

यह मानते हुए कि किसी अनुक्रम को आरंभ करने के लिए एक वैध व्युत्पत्ति है, इसे इन नियमों का उपयोग करके बढ़ाया जा सकता है। लंबाई 1 की सभी व्युत्पत्तियाँ वैध व्युत्पत्तियाँ हैं।

पुनरावर्ती पैरामीटर पास करना और उद्धृत करना

K=λq.λi.q

q को उद्धृत करता है और i को अनदेखा करता है

S=λx.λy.λz.((xz)(yz))

एक बाइनरी ट्री बनाता है जो पैरामीटर रूट से शाखाओं तक प्रवाहित हो सकता है और पहचानFunc=((SK)K) द्वारा पढ़ा जा सकता है या Kq का उपयोग करके एक उद्धृत लैम्ब्डा q पढ़ा जा सकता है।

एसकेआई अभिव्यक्ति

स्वयं-अनुप्रयोग और पुनरावर्तन

SII एक अभिव्यक्ति है जो एक तर्क लेती है और उस तर्क को स्वयं पर लागू करती है:

SIIα = Iα(Iα) = αα

इसे यू कॉम्बिनेटर के नाम से जाना जाता है। इसका एक दिलचस्प गुण यह है कि इसका स्व-प्रयोग अपरिवर्तनीय है:

SII(SII) = I(SII)(I(SII)) = SII(I(SII)) = SII(SII)

दूसरी बात यह है कि यह किसी को एक फ़ंक्शन लिखने की अनुमति देता है जो एक चीज़ को दूसरी चीज़ के स्वयं अनुप्रयोग पर लागू करता है:

(S(Kα)(SII))β = Kαβ(SIIβ) = α(Iβ(Iβ)) = α(ββ)

इस फ़ंक्शन का उपयोग प्रत्यावर्तन प्राप्त करने के लिए किया जा सकता है। यदि β वह फ़ंक्शन है जो α को किसी अन्य चीज़ के स्वयं अनुप्रयोग पर लागू करता है,

β = S(Kα)(SII)

तो इस β का स्व-अनुप्रयोग उस α का निश्चित बिंदु है:

SIIβ = ββ = α(ββ) = α(α(ββ)) = $\ldots$

यदि α कुछ ρ और ν के लिए αρν द्वारा गणना किए गए एक कम्प्यूटेशनल चरण को व्यक्त करता है, जो मानता है कि ρν' शेष गणना को व्यक्त करता है (कुछ ν' के लिए जो α ν से गणना करेगा), तो इसका निश्चित बिंदु ββ संपूर्ण पुनरावर्ती गणना को व्यक्त करता है, क्योंकि शेष गणना कॉल के लिए समान फ़ंक्शन ββ का उपयोग करना (ββν = α(ββ)ν के साथ) रिकर्सन की परिभाषा है: ρν' = ββν' = α(ββ)ν' = ...। विचलन से बचने के लिए α को किसी आधार मामले पर रुकने और पुनरावर्ती कॉल न करने के लिए किसी प्रकार की सशर्तता का उपयोग करना होगा।

इसे औपचारिक रूप दिया जा सकता है

β = 'H'α = 'S'('K'α)('SII') = 'S'('KS')'K'α('SII') = 'S'('S'(' केएस')'के')('के'('एसआईआई')) α

जैसा

'Y'α = 'SII'β = 'SII'('H'α) = 'S'('K'('SII'))'H' α = 'S'('K'('SII') ))('एस'('एस'('केएस')'के')('के'('एसआईआई'))) α

जो हमें 'Y' कॉम्बिनेटर का फिक्स्ड-पॉइंट_कॉम्बिनेटर#अन्य_फिक्स्ड-पॉइंट_कॉम्बिनेटर देता है।

उलट अभिव्यक्ति

S(K(SI))K निम्नलिखित दो शब्दों को उलट देता है:

S(K(SI))Kαβ →

K(SI)α(Kα)β →

SI(Kα)β →

Iβ(Kαβ) →

इबा →

बहुत खूब

बूलियन तर्क

एसकेआई कॉम्बिनेटर कैलकुलस बूलियन तर्क को यदि-तब-अन्यथा संरचना के रूप में भी कार्यान्वित कर सकता है। यदि-तब-अन्यथा संरचना में एक बूलियन अभिव्यक्ति शामिल होती है जो या तो सत्य ('टी') या गलत ('एफ') और दो तर्क होते हैं, जैसे:

'T'xy = x

और

'F'xy = y

कुंजी दो बूलियन अभिव्यक्तियों को परिभाषित करने में है। पहला हमारे बुनियादी कॉम्बिनेटरों में से एक की तरह ही काम करता है:

'टी' = 'के'

'K'xy = x

दूसरा भी काफी सरल है:

'एफ' = 'एसके'

'SK'xy = 'K'y(xy) = y

एक बार सत्य और असत्य परिभाषित हो जाने के बाद, सभी बूलियन तर्क को यदि-तब-अन्यथा संरचनाओं के संदर्भ में कार्यान्वित किया जा सकता है।

बूलियन 'NOT' (जो किसी दिए गए बूलियन के विपरीत रिटर्न देता है) if-then-else संरचना के समान काम करता है, जिसमें 'F' और 'T' दूसरे और तीसरे मान होते हैं, इसलिए इसे पोस्टफ़िक्स ऑपरेशन के रूप में कार्यान्वित किया जा सकता है :

'नहीं' = ('एफ')('टी') = ('एसके')('के')

यदि इसे यदि-तब-अन्यथा संरचना में रखा जाता है, तो यह दिखाया जा सकता है कि इसका अपेक्षित परिणाम है

('टी')'नहीं' = 'टी'('एफ')('टी') = 'एफ'

('एफ')'नहीं' = 'एफ'('एफ')('टी') = 'टी'

बूलियन 'OR' (जो 'T' लौटाता है यदि इसके आसपास के दो बूलियन मानों में से कोई भी 'T' है) दूसरे मान के रूप में 'T' के साथ if-then-else संरचना के समान काम करता है, इसलिए इसे इस प्रकार कार्यान्वित किया जा सकता है एक इन्फिक्स ऑपरेशन:

'या' = 'टी' = 'के'

यदि इसे यदि-तब-अन्यथा संरचना में रखा जाता है, तो यह दिखाया जा सकता है कि इसका अपेक्षित परिणाम है:

('टी')'या'('टी') = 'टी'('टी')('टी') = 'टी'

('टी')'या'('एफ') = 'टी'('टी')('एफ') = 'टी'

('एफ')'या'('टी') = 'एफ'('टी')('टी') = 'टी'

('एफ')'या'('एफ') = 'एफ'('टी')('एफ') = 'एफ'

बूलियन 'AND' (जो 'T' लौटाता है यदि इसके आसपास के दो बूलियन मान 'T' हैं) तीसरे मान के रूप में 'F' के साथ if-then-else संरचना के समान काम करता है, इसलिए इसे इस प्रकार कार्यान्वित किया जा सकता है एक पोस्टफ़िक्स ऑपरेशन:

'और' = 'एफ' = 'एसके'

यदि इसे यदि-तब-अन्यथा संरचना में रखा जाता है, तो यह दिखाया जा सकता है कि इसका अपेक्षित परिणाम है:

('टी')('टी')'और' = 'टी'('टी')('एफ') = 'टी'

('टी')('एफ')'और' = 'टी'('एफ')('एफ') = 'एफ'

('एफ')('टी')'और' = 'एफ'('टी')('एफ') = 'एफ'

('एफ')('एफ')'और' = 'एफ'('एफ')('एफ') = 'एफ'

क्योंकि यह SKI नोटेशन के संदर्भ में 'T', 'F', 'NOT' (पोस्टफ़िक्स ऑपरेटर के रूप में), 'OR' (इन्फिक्स ऑपरेटर के रूप में), और 'AND' (पोस्टफ़िक्स ऑपरेटर के रूप में) को परिभाषित करता है, इससे यह साबित होता है SKI प्रणाली बूलियन तर्क को पूरी तरह से व्यक्त कर सकती है।

चूँकि SKI कैलकुलस S-K आधार का कॉम्बिनेटरी लॉजिक#पूर्णता है, इसलिए 'NOT', 'OR' और 'AND' को उपसर्ग ऑपरेटरों के रूप में व्यक्त करना भी संभव है:

'नहीं' = 'एस'('एसआई'('केएफ'))('केटी') (जैसा कि 'एस'('एसआई'('केएफ'))('केटी')x = 'एसआई'(' KF')x('KT'x) = 'I'x('KF'x)'T' = x'FT')

'OR' = 'SI'('KT') (जैसा कि 'SI'('KT')xy = 'I'x('KT'x)y = x'T'y)

'AND' = 'SS'('K'('KF')) (as 'SS'('K'('KF'))xy = 'S'x('K'('KF')x) y = xy('KF'y) = xy'F')

अंतर्ज्ञानवादी तर्क से संबंध

कॉम्बिनेटर K और S, भावनात्मक तर्क के दो प्रसिद्ध सिद्धांतों के अनुरूप हैं:

AK: A → (B → A),

AS: (A → (B → C)) → ((A → B) → (A → C)).

फ़ंक्शन एप्लिकेशन नियम मूड सेट करना से मेल खाता है:

MP: से A और A → B, अनुमान लगाएं B.

अंतर्ज्ञानवादी तर्क के निहितार्थ खंड के लिए स्वयंसिद्ध एके और एएस, और नियम एमपी पूर्ण हैं। संयोजनात्मक तर्क को एक मॉडल के रूप में रखने के लिए:

• शास्त्रीय तर्क के निहितार्थ प्रस्तावात्मक कलन के लिए, बहिष्कृत मध्य के नियम के संयोजन एनालॉग की आवश्यकता होगी, अर्थात्, पीयर्स का नियम;
• भावात्मक तर्क, भावात्मक अभिगृहीत के संयोजनात्मक एनालॉग की आवश्यकता होगी F → A.

कॉम्बिनेटर के प्रकार और संबंधित तार्किक सिद्धांतों के बीच यह संबंध करी-हावर्ड आइसोमोर्फिज्म का एक उदाहरण है।

कमी के उदाहरण

कटौती करने के कई तरीके हो सकते हैं। सभी समान हैं, जब तक आप संचालन के क्रम को नहीं तोड़ते

• ${\textrm {SKI(KIS)}}$
  • ${\textrm {SKI(KIS)}}\Rightarrow {\textrm {K(KIS)(I(KIS))}}\Rightarrow {\textrm {K(KIS)x}}\Rightarrow {\textrm {KIS}}\Rightarrow {\textrm {I}}$
  • ${\textrm {SKI(KIS)}}\Rightarrow {\textrm {SKII}}\Rightarrow {\textrm {KI(II)}}\Rightarrow {\textrm {KII}}\Rightarrow {\textrm {I}}$
• ${\textrm {KS(I(SKSI))}}$
  • ${\textrm {KS(I(SKSI))}}\Rightarrow {\textrm {KS(I(KI(SI)))}}\Rightarrow {\textrm {KS(I(I))}}\Rightarrow {\textrm {KS(II)}}\Rightarrow {\textrm {KSI}}\Rightarrow {\textrm {S}}$
  • ${\textrm {KS(I(SKSI))}}\Rightarrow {\textrm {KS(x)}}\Rightarrow {\textrm {S}}$
• ${\textrm {SKIK}}\Rightarrow {\textrm {KK(IK)}}\Rightarrow {\textrm {KKK}}\Rightarrow {\textrm {K}}$

यह भी देखें

• संयोजन तर्क
• बी, सी, के, डब्ल्यू प्रणाली
• फिक्स्ड पॉइंट कॉम्बिनेटर
• लैम्ब्डा कैलकुलस
• कार्यात्मक प्रोग्रामिंग
• अनलैम्ब्डा प्रोग्रामिंग भाषा
• Iota और Jot प्रोग्रामिंग भाषाएं, SKI से भी अधिक सरल डिज़ाइन की गई हैं।
• मॉकिंगबर्ड का मज़ाक उड़ाना

संदर्भ

• Smullyan, Raymond (1985). To Mock a Mockingbird. Knopf. ISBN 0-394-53491-3. A gentle introduction to combinatory logic, presented as a series of recreational puzzles using bird watching metaphors.
• — (1994). "Ch. 17–20". Diagonalization and Self-Reference. Oxford University Press. ISBN 9780198534501. OCLC 473553893. are a more formal introduction to combinatory logic, with a special emphasis on fixed point results.

बाहरी संबंध

• O'Donnell, Mike "The SKI Combinator Calculus as a Universal System."
• Keenan, David C. (2001) "To Dissect a Mockingbird."
• Rathman, Chris, "Combinator Birds."
• ""Drag 'n' Drop Combinators (Java Applet)."
• A Calculus of Mobile Processes, Part I (PostScript) (by Milner, Parrow, and Walker) shows a scheme for combinator graph reduction for the SKI calculus in pages 25–28.
• the Nock programming language may be seen as an assembly language based on SK combinator calculus in the same way that traditional assembly language is based on Turing machines. Nock instruction 2 (the "Nock operator") is the S combinator and Nock instruction 1 is the K combinator. The other primitive instructions in Nock (instructions 0,3,4,5, and the pseudo-instruction "implicit cons") are not necessary for universal computation, but make programming more convenient by providing facilities for dealing with binary tree data structures and arithmetic; Nock also provides 5 more instructions (6,7,8,9,10) that could have been built out of these primitives.