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. 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). Definition. S-K Basis. Utilizing K and S combinators of the Combinatory logic, logical functions can be represented in as functions of combinators: Syntax. Backus–Naur form: Semantics. The denotational semantics of BCL may be specified as follows: where "codice_4" abbreviates  the meaning of codice_5. Here codice_6 and codice_7 are the "KS"-basis combinators, and codice_8 is the "application" operation, of combinatory logic. (The prefix codice_9 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 codice_10 (as in the present version), codice_11, codice_12, and codice_13. 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: where codice_16, codice_17, and codice_18 are arbitrary subterms. (Note, for example, that because parsing is from the left, codice_19 is not a subterm of codice_20.) BCL can be used to replicate algorithms like Turing machines and Cellular automata, BCL is Turing complete.