Binary combinatory logic: Difference between revisions
Added Further reading and universality of BCL |
Spikeylegs (talk | contribs) m →Further Readings: Added further reading Combinatory Logic |
||
Line 69: | Line 69: | ||
== Further Readings == |
== Further Readings == |
||
* {{cite journal |last1=Tromp |first1=John |title=Binary Lambda Calculus and Combinatory Logic |journal=Randomness and Complexity, From Leibniz to Chaitin |date=October 2007 |pages=237–260 |doi=10.1142/9789812770837_0014}} |
|||
* |
|||
==External links== |
==External links== |
Revision as of 18:10, 17 February 2021
This article provides insufficient context for those unfamiliar with the subject.(July 2020) |
Binary combinatory logic (BCL) is a computer programming language that uses binary terms 0 and 1 create a complete formulation of combinatory logic using only the symbols 0 and 1.[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).[1][2]
Definition
S-K Basis
Utilizing K and S combinators of the Combinatory logic, logical functions can be represented in as functions of combinators:
Boolean Algebra | S-K Basis | |
---|---|---|
True(1) | K(KK) | |
False(0) | K(K(SK))S | |
AND | SSK | |
NOT | SS(S(S(S(SK))S))(KK) | |
OR | S(SS)S(SK) | |
NAND | S(S(K(S(SS(K(KK)))))))S | |
NOR | S(S(S(SS(K(K(KK)))))(KS)) | |
XOR | S(S(S(SS)(S(S(SK)))S))K |
Syntax
<term> ::= 00 | 01 | 1 <term> <term>
Semantics
The denotational semantics of BCL may be specified as follows:
[ 00 ] == K
[ 01 ] == S
[ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )
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
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 complex algorithms like Turing machines and Cellular automata[3], BCL is Turing complete.
See also
References
Further Readings
- Tromp, John (October 2007). "Binary Lambda Calculus and Combinatory Logic". Randomness and Complexity, From Leibniz to Chaitin: 237–260. .