बाइनरी कॉम्बिनेटरी लॉजिक: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{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>
{{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"
|+List of Logical Operations as Binary Combinators<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>
|+बाइनरी कॉम्बिनेटर के रूप में लाॅजिक संचालन की सूची<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" |
!Boolean Algebra
!बूलियन बीजगणित
!S-K Basis
!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 &lt;term1> &lt;term2> ] == ( [&lt;term1>] [&lt;term2>] )</code> कहाँ<code>[...]</code>के अर्थ को संक्षिप्त करता है <code>...</code>. यहाँ <code>''K''</code> और <code>''S''</code> एसकेआई कॉम्बिनेटर कैलकुलस|केएस-बेस कॉम्बिनेटर हैं, और <code>( )</code> संयोजनात्मक तर्क का अनुप्रयोग संचालन है। (उपसर्ग <code>1</code> बाएं कोष्ठक से मेल खाता है, दायां कोष्ठक स्पष्टीकरण के लिए अनावश्यक है।)
* <code>[ 1 &lt;term1> &lt;term2> ] == ( [&lt;term1>] [&lt;term2>] )</code> कहाँ<code>[...]</code>के अर्थ को संक्षिप्त करता है, इस प्रकार यहाँ पर <code>''K''</code> और <code>''S''</code> एसकेआई कॉम्बिनेटर कैलकुलस या केएस-बेस कॉम्बिनेटर हैं, और <code>( )</code> संयोजनात्मक तर्क का अनुप्रयोग संचालन करता है। इसमें उपसर्ग <code>1</code> बाएं कोष्ठक से मेल खाता है, दायां कोष्ठक स्पष्टीकरण के लिए अनावश्यक है।


इस प्रकार बीसीएल के चार समकक्ष फॉर्मूलेशन हैं, जो ट्रिपलेट (के, एस, बाएं कोष्ठक) को एन्कोड करने के तरीके पर निर्भर करते हैं। ये <code>(00,&nbsp;01,&nbsp;1)</code> (जैसा कि वर्तमान संस्करण में है), <code>(01,&nbsp;00,&nbsp;1)</code>, <code>(10,&nbsp;11,&nbsp;0)</code>, और <code>(11,&nbsp;10,&nbsp;0)</code>.
इस प्रकार बीसीएल के चार समकक्ष फॉर्मूलेशन हैं, जो ट्रिपलेट के, एस, बाएं कोष्ठक को एन्कोड करने के तरीके पर निर्भर करते हैं। ये <code>(00,&nbsp;01,&nbsp;1)</code> <code>(01,&nbsp;00,&nbsp;1)</code>, <code>(10,&nbsp;11,&nbsp;0)</code>, और <code>(11,&nbsp;10,&nbsp;0)</code> जैसा कि वर्तमान संस्करण में है,


ईटीए-कमी (जो [[ट्यूरिंग-पूर्ण]] के लिए आवश्यक नहीं है) के अलावा, बीसीएल के [[परिचालन शब्दार्थ]] को किसी दिए गए शब्द के उप-शब्दों के लिए निम्नलिखित [[पुनर्लेखन]] नियमों द्वारा बहुत ही संक्षिप्त रूप से निर्दिष्ट किया जा सकता है, बाईं ओर से [[ पदच्छेद |पदच्छेद]] :
ईटीए-कमी जो [[ट्यूरिंग-पूर्ण]] के लिए आवश्यक नहीं है, इसके अतिरिक्त बीसीएल के [[परिचालन शब्दार्थ]] को किसी दिए गए शब्द के उप-शब्दों के लिए निम्नलिखित [[पुनर्लेखन]] नियमों द्वारा बहुत ही संक्षिप्त रूप से निर्दिष्ट किया जा सकता है, जो बाईं ओर से [[ पदच्छेद |पदच्छेदित]] हैं :
* <code> &nbsp;1100xy&nbsp;&nbsp;&rarr; x </code>
* <code> &nbsp;1100xy&nbsp;&nbsp;&rarr; x </code>
* <code> 11101xyz&nbsp;&rarr;&nbsp;11xz1yz </code>
* <code> 11101xyz&nbsp;&rarr;&nbsp;11xz1yz </code>
कहाँ <code>x</code>, <code>y</code>, और <code>z</code> मनमाने उपशब्द हैं. (ध्यान दें, उदाहरण के लिए, क्योंकि पार्सिंग बाईं ओर से है, <code>10000</code> का उपपद नहीं है <code>11010000</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" /> इस प्रकार बीसीएल [[ट्यूरिंग पूर्णता]] रहती है।


==यह भी देखें==
==यह भी देखें==
Line 68: Line 68:
* [https://tromp.github.io/cl/cl.html John's Lambda Calculus and Combinatory Logic Playground]
* [https://tromp.github.io/cl/cl.html John's Lambda Calculus and Combinatory Logic Playground]
* [http://www.ioccc.org/2012/tromp/hint.html A minimal implementation in C]
* [http://www.ioccc.org/2012/tromp/hint.html A minimal implementation in C]
* {{cite web |first=Paul |last=Brauner |title=Lambda Diagrams YouTube Playlist |website=[[YouTube]] |url=https://www.youtube.com/watch?v=koqL2nfrNAE&list=PLi8_XqluS5xc7GL-bgVrxpA2Uww6nK0gV |archive-url=https://ghostarchive.org/varchive/youtube/20211221/koqL2nfrNAE |archive-date=2021-12-21 |url-status=live}}{{cbignore}}[[Category: एल्गोरिथम सूचना सिद्धांत]] [[Category: संयोजनात्मक तर्क]]
* {{cite web |first=Paul |last=Brauner |title=Lambda Diagrams YouTube Playlist |website=[[YouTube]] |url=https://www.youtube.com/watch?v=koqL2nfrNAE&list=PLi8_XqluS5xc7GL-bgVrxpA2Uww6nK0gV |archive-url=https://ghostarchive.org/varchive/youtube/20211221/koqL2nfrNAE |archive-date=2021-12-21 |url-status=live}}{{cbignore}}


 
[[Category:CS1 English-language sources (en)]]
 
[[Category: Machine Translated Page]]
[[Category:Created On 08/07/2023]]
[[Category:Created On 08/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:एल्गोरिथम सूचना सिद्धांत]]
[[Category:संयोजनात्मक तर्क]]

Latest revision as of 10:55, 26 July 2023

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

परिभाषा

S-K बेसिस

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

बाइनरी कॉम्बिनेटर के रूप में लाॅजिक संचालन की सूची[3]
बूलियन बीजगणित 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  → 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.


अग्रिम पठन


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बाइनरी_कॉम्बिनेटरी_लॉजिक&oldid=224547’