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

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

, logical functions can be represented in as functions of combinators:

Syntax

Backus–Naur form In computer science, Backus–Naur form () or Backus normal form (BNF) is a metasyntax notation for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats ...

: ::= 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 comput ...
.  (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 execu ...
 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 Tur ...
), may be very compactly specified by the following rewriting 


In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a well-formed formula, formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewr ...
 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 Lati ...
 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 algori ...
 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 com ...
. 

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


 References



  Further reading 

* 

 External links


John's Lambda Calculus and Combinatory Logic Playground


* {{cbignore
 Algorithmic information theory
 Combinatory logic