Binary combinatory logic

Binary combinatory logic, abbreviated BCL, is a minimal formal system for expressing computation using only the two symbols 0 and 1, built on the mathematical framework of combinatory logic. Rather than relying on named variables the way lambda calculus does, combinatory logic expresses every computable function through fixed combinators, and BCL encodes these combinators, most notably the S and K combinators that together are sufficient to construct any computable function, as short binary strings. A program in BCL is therefore itself a bit string, which makes the language useful as a tool for studying program-size complexity, including Kolmogorov complexity, since the length of the shortest BCL program computing a given output provides a concrete, machine-independent way to measure that output's descriptive complexity. Because of its extreme minimality, BCL is used mainly in theoretical computer science and algorithmic information theory rather than as a practical programming language, serving as a reference model for researchers comparing the size and expressiveness of different universal computing systems.