---
title: Binary combinatory logic
slug: binary-combinatory-logic
qid: 
snapshot: enwiki-001333817043
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1333817043
tags: [11060667, 130110808, 23287509, 23603337, 24745108, 26220375, 28342700, 29176230, 7692542]
---

# Binary combinatory logic

> [!note] Provenance
> Snapshot `enwiki-001333817043` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1333817043> · Licensed CC BY-SA 4.0

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).

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== ===Syntax=== Backus–Naur form: ::= 00 | 01 | 1 ===Semantics=== The denotational semantics of BCL may be specified as follows: [ 00 ] == K [ 01 ] == S [ 1 &lt;term1> &lt;term2> ] == ( [&lt;term1>] [&lt;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,&nbsp;S,&nbsp;left parenthesis). These are (00,&nbsp;01,&nbsp;1) (as in the present version), (01,&nbsp;00,&nbsp;1) , (10,&nbsp;11,&nbsp;0) , and (11,&nbsp;10,&nbsp;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: &nbsp;1100xy&nbsp;&nbsp;&rarr; x 11101xyz&nbsp;&rarr;&nbsp;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. ==See also== Iota and Jot ==References== ==External links== John's Lambda Calculus and Combinatory Logic Playground A minimal implementation in C Lambda Calculus in 383 Bytes
