Binary combinatory logic

Binary combinatory logic (BCL) is a formulation of combinatory logic using only the symbols 0 and 1.[1] BCL has applications in the theory of program-size complexity (Kolmogorov complexity).[1][2]

Definition

Syntax

Backus–Naur form:

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

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

gollark: I suspect your foreword thing might actually be incompatible with that.
gollark: Then you would need to explicitly release it under some free software license. Which yours might not be.
gollark: Actually, the way it works is that if you program something/make some sort of creative work, you own the "intellectual property rights" or whatever to it (there's a time limit but it constantly gets extended), and have to explicitly release it as public domain/under whatever conditions for it to, well, be public domain/that.
gollark: ... it's saying what you can do with the (copyrighted) code.
gollark: It's *basically* a license in spirit.

See also

References
  1. 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.
  2. Devine, Sean (2009), "The insights of algorithmic entropy", Entropy, 11 (1): 85–110, doi:10.3390/e11010085, MR 2534819
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.