बाइनरी कॉम्बिनेटरी लॉजिक

From Vigyanwiki

बाइनरी संयोजनात्मक तर्क (बीसीएल) एक कंप्यूटर प्रोग्रामिंग भाषा है जो केवल प्रतीकों 0 और 1 का उपयोग करके कॉम्बिनेटरी लॉजिक का पूरा फॉर्मूलेशन बनाने के लिए बाइनरी शब्द 0 और 1 का उपयोग करती है।[1] एस और के कॉम्बिनेटर का उपयोग करके, जटिल बूलियन बीजगणित फ़ंक्शन बनाए जा सकते हैं। बीसीएल के पास प्रोग्राम-आकार जटिलता (कोलमोगोरोव जटिलता) के सिद्धांत में अनुप्रयोग हैं।[1][2]


परिभाषा

एस-के आधार

कॉम्बिनेटर लॉजिक के K और S कॉम्बिनेटर का उपयोग करते हुए, तार्किक कार्यों को कॉम्बिनेटर के कार्यों के रूप में दर्शाया जा सकता है:

List of Logical Operations as Binary Combinators[3]
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  → x
  • 11101xyz → 11xz1yz

कहाँ x, y, और z मनमाने उपशब्द हैं. (ध्यान दें, उदाहरण के लिए, क्योंकि पार्सिंग बाईं ओर से है, 10000 का उपपद नहीं है 11010000.)

एसके-बेसिस में नियम 110 सेल्युलर ऑटोमेटा का एक चरण (वुल्फ्राम भाषा में लिखित)।[3]

बीसीएल का उपयोग ट्यूरिंग मशीन और सेलुलर ऑटोमेटन जैसे एल्गोरिदम को दोहराने के लिए किया जा सकता है,[3]बीसीएल ट्यूरिंग पूर्णता है।

यह भी देखें

  • आयोटा और जोट

संदर्भ

  1. 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.
  2. Devine, Sean (2009), "The insights of algorithmic entropy", Entropy, 11 (1): 85–110, doi:10.3390/e11010085, MR 2534819
  3. 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.


अग्रिम पठन


बाहरी संबंध