बाइनरी कॉम्बिनेटरी लॉजिक: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Computer programming language}}बाइनरी [[संयोजनात्मक तर्क]] (बीसीएल) कंप्यूटर [[प्रोग्रामिंग भाषा]] है जो केवल | {{Short description|Computer programming language}}'''बाइनरी [[संयोजनात्मक तर्क|कॉम्बिनेटरी लॉजिक]]''' (बीसीएल) कंप्यूटर की ऐसी [[प्रोग्रामिंग भाषा]] है जो केवल 0 और 1 प्रतीकों का उपयोग करके कॉम्बिनेटरी लॉजिक का पूरा फॉर्मूलेशन बनाने के लिए बाइनरी शब्द 0 और 1 का उपयोग करती है।<ref name="tromp">{{citation|last=Tromp|first=John|title=Randomness and complexity|url=https://tromp.github.io/cl/LC.pdf|pages=237–260|year=2007|contribution=Binary lambda calculus and combinatory logic|publisher=World Sci. Publ., Hackensack, NJ|citeseerx=10.1.1.695.3142|doi=10.1142/9789812770837_0014|isbn=978-981-277-082-0|mr=2427553}}.</ref> एस और के कॉम्बिनेटर का उपयोग करके जटिल बूलियन बीजगणित फ़ंक्शन बनाए जा सकते हैं। इस प्रकार बीसीएल के पास प्रोग्राम-आकार की जटिलता को [[कोलमोगोरोव जटिलता]] के सिद्धांत में अनुप्रयोग किया जाता हैं।<ref name="tromp"/><ref>{{citation |last=Devine |first=Sean |doi=10.3390/e11010085 |issue=1 |journal=Entropy |mr=2534819 |pages=85–110 |title=The insights of algorithmic entropy |volume=11 |year=2009 |doi-access=free }}</ref> | ||
==परिभाषा== | ==परिभाषा== | ||
=== | === S-K बेसिस === | ||
कॉम्बिनेटर लॉजिक के K और S कॉम्बिनेटर का उपयोग करते हुए, | कॉम्बिनेटर लॉजिक के K और S कॉम्बिनेटर का उपयोग करते हुए, लाॅजिक से जुड़े कार्यों को कॉम्बिनेटर के कार्यों के रूप में दर्शाया जा सकता है: | ||
{| class="wikitable" | {| class="wikitable" | ||
|+ | |+बाइनरी कॉम्बिनेटर के रूप में लाॅजिक संचालन की सूची<ref name=":0">{{Cite web|last=Wolfram|first=Stephen|date=2021-12-06|title=Combinators: A Centennial View|url=https://writings.stephenwolfram.com/2020/12/combinators-a-centennial-view/|url-status=live|access-date=2021-02-17|website=writings.stephenwolfram.com|language=en|archive-url=https://web.archive.org/web/20201206200216/https://writings.stephenwolfram.com/2020/12/combinators-a-centennial-view/ |archive-date=2020-12-06 }}</ref> | ||
! rowspan="5" | | ! rowspan="5" | | ||
! | !बूलियन बीजगणित | ||
!S-K | !S-K बेसिस | ||
|- | |- | ||
|True(1) | |True(1) | ||
| Line 38: | Line 38: | ||
!S(S(S(SS)(S(S(SK)))S))K | !S(S(S(SS)(S(S(SK)))S))K | ||
|} | |} | ||
=== | ===प्रारूप=== | ||
बैकस | बैकस नौर फॉर्म: | ||
<syntaxhighlight lang="bnf"> <term> ::= 00 | 01 | 1 <term> <term> </syntaxhighlight> | <syntaxhighlight lang="bnf"> <term> ::= 00 | 01 | 1 <term> <term> </syntaxhighlight> | ||
===शब्दार्थ=== | ===शब्दार्थ=== | ||
बीसीएल के [[सांकेतिक शब्दार्थ]] को इस प्रकार निर्दिष्ट किया जा सकता है: | बीसीएल के [[सांकेतिक शब्दार्थ]] को इस प्रकार निर्दिष्ट किया जा सकता है: | ||
* <code>[ 00 ] == ''K''</code> * <code>[ 01 ] == ''S''</code> | * <code>[ 00 ] == ''K''</code> * <code>[ 01 ] == ''S''</code> | ||
* <code>[ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )</code> कहाँ<code>[...]</code>के अर्थ को संक्षिप्त करता है | * <code>[ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )</code> कहाँ<code>[...]</code>के अर्थ को संक्षिप्त करता है, इस प्रकार यहाँ पर <code>''K''</code> और <code>''S''</code> एसकेआई कॉम्बिनेटर कैलकुलस या केएस-बेस कॉम्बिनेटर हैं, और <code>( )</code> संयोजनात्मक तर्क का अनुप्रयोग संचालन करता है। इसमें उपसर्ग <code>1</code> बाएं कोष्ठक से मेल खाता है, दायां कोष्ठक स्पष्टीकरण के लिए अनावश्यक है। | ||
इस प्रकार बीसीएल के चार समकक्ष फॉर्मूलेशन हैं, जो ट्रिपलेट | इस प्रकार बीसीएल के चार समकक्ष फॉर्मूलेशन हैं, जो ट्रिपलेट के, एस, बाएं कोष्ठक को एन्कोड करने के तरीके पर निर्भर करते हैं। ये <code>(00, 01, 1)</code> <code>(01, 00, 1)</code>, <code>(10, 11, 0)</code>, और <code>(11, 10, 0)</code> जैसा कि वर्तमान संस्करण में है, | ||
ईटीए-कमी | ईटीए-कमी जो [[ट्यूरिंग-पूर्ण]] के लिए आवश्यक नहीं है, इसके अतिरिक्त बीसीएल के [[परिचालन शब्दार्थ]] को किसी दिए गए शब्द के उप-शब्दों के लिए निम्नलिखित [[पुनर्लेखन]] नियमों द्वारा बहुत ही संक्षिप्त रूप से निर्दिष्ट किया जा सकता है, जो बाईं ओर से [[ पदच्छेद |पदच्छेदित]] हैं : | ||
* <code> 1100xy → x </code> | * <code> 1100xy → x </code> | ||
* <code> 11101xyz → 11xz1yz </code> | * <code> 11101xyz → 11xz1yz </code> | ||
जहाँ <code>x</code>, <code>y</code>, और <code>z</code> उपशब्द हैं, यहाँ पर ध्यान दें, उदाहरण के लिए पार्सिंग बाईं ओर से है, जिसके लिए <code>10000</code> <code>11010000</code> का उपपद नहीं है। | |||
[[File:Rule 110 SK Basis.png|thumb|401x401px|एसके-बेसिस में नियम 110 सेल्युलर ऑटोमेटा का चरण (वुल्फ्राम भाषा में लिखित)।<ref name=":0" />]]बीसीएल का उपयोग [[ट्यूरिंग मशीन]] और [[ सेलुलर ऑटोमेटन |सेलुलर ऑटोमेटन]] जैसे एल्गोरिदम को दोहराने के लिए किया जा सकता है,<ref name=":0" />बीसीएल [[ट्यूरिंग पूर्णता]] है। | [[File:Rule 110 SK Basis.png|thumb|401x401px|एसके-बेसिस में नियम 110 सेल्युलर ऑटोमेटा का चरण (वुल्फ्राम भाषा में लिखित)।<ref name=":0" />]]बीसीएल का उपयोग [[ट्यूरिंग मशीन]] और [[ सेलुलर ऑटोमेटन |सेलुलर ऑटोमेटन]] जैसे एल्गोरिदम को दोहराने के लिए किया जा सकता है,<ref name=":0" /> इस प्रकार बीसीएल [[ट्यूरिंग पूर्णता]] रहती है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
Revision as of 16:49, 16 July 2023
बाइनरी कॉम्बिनेटरी लॉजिक (बीसीएल) कंप्यूटर की ऐसी प्रोग्रामिंग भाषा है जो केवल 0 और 1 प्रतीकों का उपयोग करके कॉम्बिनेटरी लॉजिक का पूरा फॉर्मूलेशन बनाने के लिए बाइनरी शब्द 0 और 1 का उपयोग करती है।[1] एस और के कॉम्बिनेटर का उपयोग करके जटिल बूलियन बीजगणित फ़ंक्शन बनाए जा सकते हैं। इस प्रकार बीसीएल के पास प्रोग्राम-आकार की जटिलता को कोलमोगोरोव जटिलता के सिद्धांत में अनुप्रयोग किया जाता हैं।[1][2]
परिभाषा
S-K बेसिस
कॉम्बिनेटर लॉजिक के K और S कॉम्बिनेटर का उपयोग करते हुए, लाॅजिक से जुड़े कार्यों को कॉम्बिनेटर के कार्यों के रूप में दर्शाया जा सकता है:
| बूलियन बीजगणित | S-K बेसिस | |
|---|---|---|
| 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 का उपपद नहीं है।
एसके-बेसिस में नियम 110 सेल्युलर ऑटोमेटा का चरण (वुल्फ्राम भाषा में लिखित)।[3]
बीसीएल का उपयोग ट्यूरिंग मशीन और सेलुलर ऑटोमेटन जैसे एल्गोरिदम को दोहराने के लिए किया जा सकता है,[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.
