{
  "id": "enwiki-001333817043",
  "slug": "binary-combinatory-logic",
  "title": "Binary combinatory logic",
  "qid": "",
  "lead": "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).",
  "body": "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",
  "categories": [
    "11060667",
    "130110808",
    "23287509",
    "23603337",
    "24745108",
    "26220375",
    "28342700",
    "29176230",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1333817043",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1768858809.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001333817043",
    "type": "webpage",
    "title": "Binary combinatory logic",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/binary-combinatory-logic",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001333817043",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1333817043",
    "note": "Immutable snapshot enwiki-001333817043"
  }
}