Binary combinatory logic

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

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

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

Syntax

Backus–Naur form: ::= 00 | 01 | 1

Semantics

The denotational semantics of BCL may be specified as follows: [ 00 ]

K [ 01 ]

S [ 1 ] == ( [] [] ) 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, BCL is Turing complete.

See also

Iota and Jot

John's Lambda Calculus and Combinatory Logic Playground A minimal implementation in C Lambda Calculus in 383 Bytes

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

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.