Binary combinatory logic
Binary combinatory logic 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.
Definition
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 | K | |
| False | K | |
| AND | SSK | |
| NOT | SS) | |
| OR | SS | |
| NAND | S))))S | |
| NOR | S))) | |
| XOR | S)K |
Syntax
Backus–Naur form:Semantics
The denotational semantics of BCL may be specified as follows: K S, where "
...". Here K and S are the KS-basis combinators, and Thus there are four equivalent formulations of BCL, depending on the manner of encoding the triplet. These are
The operational semantics of BCL, apart from eta-reduction, 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. BCL can be used to replicate algorithms like Turing machines and Cellular automata, BCL is Turing complete.