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

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

लैम्ब्डा कैलकुलस में सभी ऑपरेशनों को कॉम्बिनेटरी लॉजिक S-के आधार के पूर्ण स्वरूप के माध्यम से SKI कैलकुलस में द्विआधारी ट्री के रूप में एन्कोड किया जा सकता है, जिनकी पत्तियाँ तीन प्रतीकों S, के, और आई में से हैं, जिन्हें कॉम्बिनेटर कहा जाता है।

संकेतन

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

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

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

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

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

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

'I'X = X

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

'K'XY = x

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

'S'XYz = xz(Yz)

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

सभी ट्री x और सभी ट्री Y के लिए, 'SK'XY सदैव दो चरणों में Y का मूल्यांकन करेगा, इस प्रकार 'K'Y(XY) = Y, इसलिए 'SK'XY के मूल्यांकन का अंतिम परिणाम सदैव Y के मूल्यांकन के परिणाम के बराबर होगा। इस प्रकार हम कहते हैं कि 'SK'X और 'I' कार्यात्मक रूप से समतुल्य हैं क्योंकि किसी भी Y पर लागू होने पर वे सदैव ही परिणाम देते हैं।

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

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

ιx = x'SK'

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

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

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

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

1. S, K, और I पद हैं।
2. यदि τ₁ और T₂ पद हैं, तो (τ₁τ₂) शब्द है.
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 पढ़ा जा सकता है।

SKI अभिव्यक्ति

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

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

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

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

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'(' केS')'K')('K'('Sआईआई')) α

जैसा

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

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

व्युत्क्रम अभिव्यक्ति

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

S(K(SI))Kαβ →

K(SI)α(Kα)β →

SI(Kα)β →

Iβ(Kαβ) →

Iβα →

βα

बूलियन तर्क

SKI कॉम्बिनेटर कैलकुलस बूलियन तर्क को if-then-else संरचना के रूप में भी कार्यान्वित कर सकता है। if-then-else संरचना में बूलियन अभिव्यक्ति सम्मिलित होती है जो या तो सत्य ('T') या गलत ('F') और दो तर्क होते हैं, जैसे:

'T'XY = x

और

'F'XY = Y

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

'T' = 'K'

'K'XY = x

इसके लिए दूसरा मान भी अत्यधिक सरल है:

'F' = 'SK'

'SK'XY = 'K'Y(XY) = Y

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

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

NOT = (F)(T) = (SK)(K)

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

(T)NOT = T(F)(T) = F

(F)NOT = F(F)(T) = T

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

OR = T = K

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

(T)OR(T) = T(T)(T) = T

(T)OR(F) = T(T)(F) = T

(F)OR(T) = F(T)(T) = T

(F)OR(F) = F(T)(F) = F

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

AND = F = SK

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

(T)(T)AND = T(T)(F) = T

(T)(F)AND = T(F)(F) = F

(F)(T)AND = F(T)(F) = F

(F)(F)AND = F(F)(F) = F

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

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

NOT = S(SI(KF))(KT) (as S(SI(KF))(KT)x = SI(KF)x(KTx) = Ix(KFx)T = xFT)

OR = SI(KT) (as SI(KT)xy = Ix(KTx)y = xTy)

AND = SS(K(KF)) (as SS(K(KF))xy = Sx(K(KF)x)y = xy(KFy) = xyF)

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

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

AK: A → (B → A),

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

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

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

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

• मौलिक तर्क के निहितार्थ प्रस्तावात्मक कलन के लिए, बहिष्कृत मध्य के नियम के संयोजन एनालॉग की आवश्यकता होगी, अर्थात्, पीयर्स का नियम;
• भावात्मक तर्क, भावात्मक अभिगृहीत के संयोजनात्मक एनालॉग 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.