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.

Uses your system voice; voice and rate in settings.

≈ 4 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.[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).[1][2]

  • 2 See also
  • 3 References
  • 4 Further reading
  • 5 External links
  • Definition

    edit edit source

    S-K Basis

    edit edit source

    Utilizing K and S combinators of the 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

    edit edit source

    Backus–Naur form:

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

    Semantics

    edit edit source

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

    BCL can be used to replicate algorithms like Turing machines and Cellular automata,[3] BCL is Turing complete.

    See also

    edit edit source

    References

    edit edit source
    1. ^ a b Tromp, John (2007), "Binary lambda calculus and combinatory logic", Randomness and complexity (PDF), World Sci. Publ., Hackensack, NJ, pp. 237–260, CiteSeerX 10.1.1.695.3142, doi:10.1142/9789812770837_0014, ISBN 978-981-277-082-0, MR 2427553 {{citation}}: Cite uses deprecated parameter |citeseerx= (help). Wikipedia revision 1333817043, retrieved 2026-11-20
    2. ^ Devine, Sean (2009), "The insights of algorithmic entropy", Entropy, 11 (1): 85–110, Bibcode:2009Entrp..11...85D, doi:10.3390/e11010085, MR 2534819 Wikipedia revision 1333817043, retrieved 2026-11-20
    3. ^ a b c Wolfram, Stephen (2021-12-06). "Combinators: A Centennial View". writings.stephenwolfram.com. arXiv:2103.12811. Archived from the original on 2020-12-06. Retrieved 2021-02-17. Wikipedia revision 1333817043, retrieved 2026-11-20

    Further reading

    edit edit source edit edit source

    Text derived from https://en.wikipedia.org/w/index.php?oldid=1333817043 under CC BY-SA 4.0; modifications have been made.

    Words in each sectionDefinitionDefinitionDefinition: 320 words320Further readingFurther readingFurther reading: 54 words54See alsoSee alsoSee also: 6 words6
    Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

    Provenance

    snapshot enwiki-001333817043 · captured 2026-01-19 · ledger · version history

    Cite this page as: encyclopegia.org, “Binary combinatory logic”, snapshot enwiki-001333817043. https://encyclopegia.org/a/binary-combinatory-logic