Binary combinatory logic
Computer programming language
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. 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).
01Definition
S-K Basis
Utilizing 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
<term> ::= 00 | 01 | 1 <term> <term>Semantics
The 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 → x
- 11101xyz → 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, BCL is Turing complete.
Sources and credits
This article is adapted from the Wikipedia article “Binary combinatory logic”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Images, from Wikimedia Commons:
- Rule 110 SK Basis.png by Stephen Wolfram, CC BY-SA 4.0
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.