Binary combinatory logic (BCL) is a computer

programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...

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 In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produ ...

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: ::= 00 , 01 , 1

Semantics

The denotational semantics 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 


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 execut ...
 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 computer's instruction set, a programming language, or a  cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tu ...
), may be very compactly specified by the following  rewriting rules for subterms of a given term, parsing 

Parsing, syntax analysis, or syntactic analysis is the process of analyzing a  string of  symbols, either in  natural language, computer languages or  data structures, conforming to the rules of a formal grammar.  The term ''parsing'' comes from L ...
 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 algor ...
 and Cellular automata 



A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
, BCL is Turing complete 






Alan Mathison Turing  (; 23 June 1912 – 7 June 1954) was an English mathematician,  computer scientist, logician, cryptanalyst, philosopher, and  theoretical biologist. Turing was highly influential in the development of theoretical co ...
. 

 See also

*  Iota and Jot

 References



  Further reading 

* 

 External links


John's Lambda Calculus and Combinatory Logic Playground


* {{cbignore
 Algorithmic information theory
 Combinatory logic