Binary combinatory logic

---

title: "Binary combinatory logic" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["algorithmic-information-theory", "combinatory-logic"] description: "Computer programming language" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Binary_combinatory_logic" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Computer programming language ::

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: ::data[format=table title="List of Logical Operations as Binary Combinators{{Cite journal|last=Wolfram|first=Stephen|date=2021-12-06|title=Combinators: A Centennial View|url=https://writings.stephenwolfram.com/2020/12/combinators-a-centennial-view/|url-status=live|access-date=2021-02-17|website=writings.stephenwolfram.com|arxiv=2103.12811 |language=en|archive-url=https://web.archive.org/web/20201206200216/https://writings.stephenwolfram.com/2020/12/combinators-a-centennial-view/ |archive-date=2020-12-06 }}"]

Boolean Algebra	S-K Basis	K(KK)	K(K(SK))	SSK	SS(S(S(S(SK))S))(KK)	S(SS)S(SK)	S(S(K(S(SS(K(KK)))))))S	S(S(S(SS(K(K(KK)))))(KS))	S(S(S(SS)(S(S(SK)))S))K
True(1)
False(0)
AND
NOT
OR
NAND
NOR
XOR
::

Syntax

Backus–Naur form: ::code[lang=bnf] ::= 00 | 01 | 1

===Semantics=== The [[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 [[SKI combinator calculus|''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, 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]] of BCL, apart from eta-reduction (which is not required for [[Turing-complete|Turing completeness]]), 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. (Note, for example, that because parsing is from the left, 10000 is not a subterm of 11010000.) [[File:Rule 110 SK Basis.png|thumb|401x401px|One step of Rule 110 Cellular Automata in SK-Basis(Written in the [[Wolfram Language]]).]] BCL can be used to replicate algorithms like [[Turing machine|Turing machines]] and [[Cellular automaton|Cellular automata]], BCL is [[Turing completeness|Turing complete]].

==See also==

• [[Iota and Jot]]

==References== {{reflist}}

== Further reading ==

• {{cite journal |last1=Tromp |first1=John |title=Binary Lambda Calculus and Combinatory Logic |journal=Randomness and Complexity, from Leibniz to Chaitin |date=October 2007 |pages=237–260 |doi=10.1142/9789812770837_0014|isbn=978-981-277-082-0 |url=https://drops.dagstuhl.de/opus/volltexte/2006/628/ }}
• {{cite web |first=John |last=Tromp |title=Functional Bits: Lambda Calculus based Algorithmic Information Theory |date=April 2023 |publisher=tromp.github.io |url=http://tromp.github.io/cl/LC.pdf}}

==External links==

• [https://tromp.github.io/cl/cl.html John's Lambda Calculus and Combinatory Logic Playground]
• [http://www.ioccc.org/2012/tromp/hint.html A minimal implementation in C]
• [https://justine.lol/lambda Lambda Calculus in 383 Bytes]
• {{cite web |first=Paul |last=Brauner |title=Lambda Diagrams YouTube Playlist |website=[[YouTube]] |date=10 January 2018 |url=https://www.youtube.com/watch?v=koqL2nfrNAE&list=PLi8_XqluS5xc7GL-bgVrxpA2Uww6nK0gV |archive-url=https://ghostarchive.org/varchive/youtube/20211221/koqL2nfrNAE |archive-date=2021-12-21 |url-status=live}}{{cbignore}} [[Category:Algorithmic information theory]] [[Category:Combinatory logic]] ::

References

1. Tromp, John. (2007). "Randomness and complexity". World Sci. Publ., Hackensack, NJ.
2. Devine, Sean. (2009). "The insights of algorithmic entropy". Entropy.
3. Wolfram, Stephen. (2021-12-06). "Combinators: A Centennial View".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::