Binary combinatory logic (BCL) is a computer

programming language A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...

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:

Syntax

Backus–Naur form In computer science, Backus–Naur form (BNF, pronounced ), also known as Backus normal form, is a notation system for defining the Syntax (programming languages), syntax of Programming language, programming languages and other Formal language, for ...

: ::= 00 , 01 , 1

Semantics

The

denotational semantics In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...

of BCL may be specified as follows: *

 00 
 ''K''

 01 
 ''S''

 1 <term1> <term2> 
 (  lt;term1> lt;term2>)

where "

 ../code>" 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 

Parsing, syntax analysis, or syntactic analysis is a process of analyzing a String (computer science), string of Symbol (formal), symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal gramm ...
 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

 References



  Further reading 

* 
* 

 External links


John's Lambda Calculus and Combinatory Logic Playground



Lambda Calculus in 383 Bytes
* {{cbignore
 Algorithmic information theory
 Combinatory logic