बाइनरी कॉम्बिनेटरी लॉजिक
बाइनरी संयोजनात्मक तर्क (बीसीएल) कंप्यूटर प्रोग्रामिंग भाषा है जो केवल प्रतीकों 0 और 1 का उपयोग करके कॉम्बिनेटरी लॉजिक का पूरा फॉर्मूलेशन बनाने के लिए बाइनरी शब्द 0 और 1 का उपयोग करती है।[1] एस और के कॉम्बिनेटर का उपयोग करके, जटिल बूलियन बीजगणित फ़ंक्शन बनाए जा सकते हैं। बीसीएल के पास प्रोग्राम-आकार जटिलता (कोलमोगोरोव जटिलता) के सिद्धांत में अनुप्रयोग हैं।[1][2]
परिभाषा
एस-के आधार
कॉम्बिनेटर लॉजिक के K और S कॉम्बिनेटर का उपयोग करते हुए, तार्किक कार्यों को कॉम्बिनेटर के कार्यों के रूप में दर्शाया जा सकता है:
| Boolean Algebra | S-K Basis | |
|---|---|---|
| True(1) | K(KK) | |
| False(0) | K(K(SK)) | |
| AND | SSK | |
| NOT | SS(S(S(S(SK))S))(KK) | |
| OR | S(SS)S(SK) | |
| NAND | S(S(K(S(SS(K(KK)))))))S | |
| NOR | S(S(S(SS(K(K(KK)))))(KS)) | |
| XOR | S(S(S(SS)(S(S(SK)))S))K |
सिंटेक्स
बैकस-नौर फॉर्म:
<term> ::= 00 | 01 | 1 <term> <term>
शब्दार्थ
बीसीएल के सांकेतिक शब्दार्थ को इस प्रकार निर्दिष्ट किया जा सकता है:
[ 00 ] == K*[ 01 ] == S[ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )कहाँ[...]के अर्थ को संक्षिप्त करता है.... यहाँKऔरSएसकेआई कॉम्बिनेटर कैलकुलस|केएस-बेस कॉम्बिनेटर हैं, और( )संयोजनात्मक तर्क का अनुप्रयोग संचालन है। (उपसर्ग1बाएं कोष्ठक से मेल खाता है, दायां कोष्ठक स्पष्टीकरण के लिए अनावश्यक है।)
इस प्रकार बीसीएल के चार समकक्ष फॉर्मूलेशन हैं, जो ट्रिपलेट (के, एस, बाएं कोष्ठक) को एन्कोड करने के तरीके पर निर्भर करते हैं। ये (00, 01, 1) (जैसा कि वर्तमान संस्करण में है), (01, 00, 1), (10, 11, 0), और (11, 10, 0).
ईटीए-कमी (जो ट्यूरिंग-पूर्ण के लिए आवश्यक नहीं है) के अलावा, बीसीएल के परिचालन शब्दार्थ को किसी दिए गए शब्द के उप-शब्दों के लिए निम्नलिखित पुनर्लेखन नियमों द्वारा बहुत ही संक्षिप्त रूप से निर्दिष्ट किया जा सकता है, बाईं ओर से पदच्छेद :
1100xy → x11101xyz → 11xz1yz
कहाँ x, y, और z मनमाने उपशब्द हैं. (ध्यान दें, उदाहरण के लिए, क्योंकि पार्सिंग बाईं ओर से है, 10000 का उपपद नहीं है 11010000.)
बीसीएल का उपयोग ट्यूरिंग मशीन और सेलुलर ऑटोमेटन जैसे एल्गोरिदम को दोहराने के लिए किया जा सकता है,[3]बीसीएल ट्यूरिंग पूर्णता है।
यह भी देखें
- आयोटा और जोट
संदर्भ
- ↑ 1.0 1.1 Tromp, John (2007), "Binary lambda calculus and combinatory logic", Randomness and complexity (PDF), World Sci. Publ., Hackensack, NJ, pp. 237–260, CiteSeerX 10.1.1.695.3142, doi:10.1142/9789812770837_0014, ISBN 978-981-277-082-0, MR 2427553.
- ↑ Devine, Sean (2009), "The insights of algorithmic entropy", Entropy, 11 (1): 85–110, doi:10.3390/e11010085, MR 2534819
- ↑ 3.0 3.1 3.2 Wolfram, Stephen (2021-12-06). "Combinators: A Centennial View". writings.stephenwolfram.com (in English). Archived from the original on 2020-12-06. Retrieved 2021-02-17.
अग्रिम पठन
- Tromp, John (October 2007). "Binary Lambda Calculus and Combinatory Logic". Randomness and Complexity, from Leibniz to Chaitin: 237–260. doi:10.1142/9789812770837_0014. ISBN 978-981-277-082-0.
बाहरी संबंध
- John's Lambda Calculus and Combinatory Logic Playground
- A minimal implementation in C
- Brauner, Paul. "Lambda Diagrams YouTube Playlist". YouTube. Archived from the original on 2021-12-21.
