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 Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of com ...

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 Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of com ...

, 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 


Combinatory logic is a notation to eliminate the need for  quantified variables in mathematical logic. It was introduced by  Moses Schönfinkel and  Haskell Curry, and has more recently been used in computer science as a theoretical  model of com ...
.  (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 


Operational semantics is a category of  formal programming language semantics in which certain desired properties of a  program, such as correctness, safety or security, are  verified by constructing  proofs from logical statements about its exec ...
 of BCL, apart from eta-reduction (which is not required for Turing completeness 



In computability theory, a system of data-manipulation rules (such as a  model of computation, a computer's instruction set, a programming language, or a  cellular automaton) is said to be Turing-complete or computationally universal if it can b ...
), 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 





A Turing machine is a  mathematical model of computation describing an  abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any  computer alg ...
 and  Cellular automata, BCL is  Turing complete. 

 See also

* Iota and Jot 

In formal language theory and computer science, Iota and Jot (from  Greek iota ι, Hebrew  yodh י, the smallest letters in those two alphabets) are languages, extremely minimalist formal systems, designed to be even simpler than other more popula ...


 References



  Further reading 

* 
* 

 External links


John's Lambda Calculus and Combinatory Logic Playground



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