# Binary combinatory logic

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Binary_combinatory_logic
> Markdown URL: https://mediated.wiki/source/Binary_combinatory_logic.md
> Source: https://en.wikipedia.org/wiki/Binary_combinatory_logic
> Source revision: 1333817043
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

**Binary combinatory logic** (**BCL**) is a computer [programming language](/source/Programming_language) that uses binary terms 0 and 1 to create a complete formulation of [combinatory logic](/source/Combinatory_logic) using only the symbols 0 and 1.[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](/source/Kolmogorov_complexity)).[1][2]

## Definition

### S-K Basis

Utilizing **K** and **S** combinators of the [Combinatory logic](/source/Combinatory_logic), logical functions can be represented in as functions of combinators:

List of Logical Operations as Binary Combinators[3] 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

[Backus–Naur form](/source/Backus%E2%80%93Naur_form):

 <term> ::= 00 | 01 | 1 <term> <term>

### Semantics

The [denotational semantics](/source/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](/source/SKI_combinator_calculus), and ( ) is the *application* operation, of [combinatory logic](/source/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](/source/Operational_semantics) of BCL, apart from eta-reduction (which is not required for [Turing completeness](/source/Turing-complete)), may be very compactly specified by the following [rewriting](/source/Rewriting) rules for subterms of a given term, [parsing](/source/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](/source/Turing_machine) and [Cellular automata](/source/Cellular_automaton),[3] BCL is [Turing complete](/source/Turing_completeness).

## See also

- [Iota and Jot](/source/Iota_and_Jot)

## References

1. Tromp, John (2007), ["Binary lambda calculus and combinatory logic"](https://tromp.github.io/cl/LC.pdf), *Randomness and complexity*, World Sci. Publ., Hackensack, NJ, pp. 237–260, [CiteSeerX 10.1.1.695.3142](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.695.3142). [doi:10.1142/9789812770837_0014](https://doi.org/10.1142/9789812770837_0014). ISBN 978-981-277-082-0. MR 2427553.

1. Devine, Sean (2009), "The insights of algorithmic entropy", *Entropy*. **11** (1): 85–110, [Bibcode:2009Entrp..11...85D](https://ui.adsabs.harvard.edu/abs/2009Entrp..11...85D). [doi:10.3390/e11010085](https://doi.org/10.3390/e11010085). MR 2534819

1. Wolfram, Stephen (2021-12-06). ["Combinators: A Centennial View"](https://writings.stephenwolfram.com/2020/12/combinators-a-centennial-view/). *writings.stephenwolfram.com*. [arXiv:2103.12811](https://arxiv.org/abs/2103.12811). [Archived](https://web.archive.org/web/20201206200216/https://writings.stephenwolfram.com/2020/12/combinators-a-centennial-view/) 2020-12-06 at the Wayback Machine. Retrieved 2021-02-17.

## Further reading

- Tromp, John (October 2007). ["Binary Lambda Calculus and Combinatory Logic"](https://drops.dagstuhl.de/opus/volltexte/2006/628/). *Randomness and Complexity, from Leibniz to Chaitin*. [doi:10.1142/9789812770837_0014](https://doi.org/10.1142/9789812770837_0014). ISBN 978-981-277-082-0.
- Tromp, John (April 2023). ["Functional Bits: Lambda Calculus based Algorithmic Information Theory"](http://tromp.github.io/cl/LC.pdf). tromp.github.io.

## External links

- [John's Lambda Calculus and Combinatory Logic Playground](https://tromp.github.io/cl/cl.html)
- [A minimal implementation in C](http://www.ioccc.org/2012/tromp/hint.html)
- [Lambda Calculus in 383 Bytes](https://justine.lol/lambda)
- Brauner, Paul (10 January 2018). ["Lambda Diagrams YouTube Playlist"](https://www.youtube.com/watch?v=koqL2nfrNAE&list=PLi8_XqluS5xc7GL-bgVrxpA2Uww6nK0gV). *[YouTube](/source/YouTube)*. [Archived](https://ghostarchive.org/varchive/youtube/20211221/koqL2nfrNAE) 2021-12-21 at the Wayback Machine.

---
Adapted from the Wikipedia article [Binary combinatory logic](https://en.wikipedia.org/wiki/Binary_combinatory_logic) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Binary_combinatory_logic?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.