Binary combinatory logic
Binary combinatory logic (BCL) is a computer programming language that uses binary terms 0 and 1 to create a complete formulation of combinatory logic using only the symbols 0 and 1.
≈ 4 min read
Binary combinatory logic. encyclopegia.org, snapshot enwiki-001333817043. /a/binary-combinatory-logic
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Binary combinatory logic (BCL) is a computer programming language that uses binary terms 0 and 1 to create a complete formulation of combinatory logic using only the symbols 0 and 1.[1] Using the S and K combinators, complex Boolean algebra functions can be made. BCL has applications in the theory of program-size complexity (Kolmogorov complexity).[1][2]
Definition
edit edit sourceS-K Basis
edit edit sourceUtilizing K and S combinators of the Combinatory logic, logical functions can be represented in as functions of combinators:
| 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 |
Syntax
edit edit source <term> ::= 00 | 01 | 1 <term> <term>Semantics
edit edit sourceThe denotational semantics of BCL may be specified as follows:
[ 00 ] == K[ 01 ] == S[ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )
where "[...]" abbreviates "the meaning of ...". Here K and S are the KS-basis combinators, and ( ) is the application operation, of combinatory logic. (The prefix 1 corresponds to a left parenthesis, right parentheses being unnecessary for disambiguation.)
Thus there are four equivalent formulations of BCL, depending on the manner of encoding the triplet (K, S, left parenthesis). These are (00, 01, 1) (as in the present version), (01, 00, 1), (10, 11, 0), and (11, 10, 0).
The operational semantics of BCL, apart from eta-reduction (which is not required for Turing completeness), may be very compactly specified by the following rewriting rules for subterms of a given term, parsing from the left:
1100xy → x11101xyz → 11xz1yz
where x, y, and z are arbitrary subterms. (Note, for example, that because parsing is from the left, 10000 is not a subterm of 11010000.)
BCL can be used to replicate algorithms like Turing machines and Cellular automata,[3] BCL is Turing complete.
See also
edit edit sourceReferences
edit edit source- ^ a b 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
{{citation}}: Cite uses deprecated parameter|citeseerx=(help). Wikipedia revision 1333817043, retrieved 2026-11-20 - ^ Devine, Sean (2009), "The insights of algorithmic entropy", Entropy, 11 (1): 85–110, Bibcode:2009Entrp..11...85D, doi:10.3390/e11010085, MR 2534819 Wikipedia revision 1333817043, retrieved 2026-11-20
- ^ a b c Wolfram, Stephen (2021-12-06). "Combinators: A Centennial View". writings.stephenwolfram.com. arXiv:2103.12811. Archived from the original on 2020-12-06. Retrieved 2021-02-17. Wikipedia revision 1333817043, retrieved 2026-11-20
Further reading
edit edit source- 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.
{{cite journal}}: CS1 maint: periodical has ISBN (link) - Tromp, John (April 2023). "Functional Bits: Lambda Calculus based Algorithmic Information Theory" (PDF). tromp.github.io.
External links
edit edit source- John's Lambda Calculus and Combinatory Logic Playground
- A minimal implementation in C
- Lambda Calculus in 383 Bytes
- Brauner, Paul (10 January 2018). "Lambda Diagrams YouTube Playlist". YouTube. Archived from the original on 2021-12-21.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1333817043 under CC BY-SA 4.0; modifications have been made.