Binary combinatory logic

Binary combinatory logic

Binary combinatory logic (BCL) is a formulation of combinatory logic using only the symbols 0 and 1. BCL has applications in the theory of program-size complexity (Kolmogorov complexity).

Definition

yntax

Backus–Naur form:
* ::= 00 | 01 | 1

emantics

The denotational semantics of BCL may be specified as follows:
* [ 00 ] = "K"
* [ 01 ] = "S"
* [ 1 ] = "(" [] [] ")" 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 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 from the left:
* 1100xy ightarrow x
* 11101xyz ightarrow 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.)

ee also

* Iota and Jot

External links

* [http://homepages.cwi.nl/~tromp/cl/cl.html John's Lambda Calculus and Combinatory Logic Playground]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Combinatory logic — Not to be confused with combinational logic, a topic in digital electronics. Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been… …   Wikipedia

  • Turing tarpit — Turing tar pit is a general term for a programming language designed to be Turing complete while in some sense simplifying to the greatest extent possible both the syntax and the semantics of the language. Such a language gives up certain… …   Wikipedia

  • Iota and Jot — Iota and its successor Jot (from Greek iota, Hebrew yodh, the smallest letters in those two alphabets) are Turing tarpits, esoteric programming languages that are designed to be as small as possible but still Turing complete. Each uses two… …   Wikipedia

  • Outline of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

  • List of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

  • SKI combinator calculus — is a computational system that is a reduced, untyped version of Lambda calculus. All operations in Lambda calculus are expressed in SKI as binary trees whose leaves are one of the three symbols S, K, and I (called combinators). In fact, the… …   Wikipedia

  • Function (mathematics) — f(x) redirects here. For the band, see f(x) (band). Graph of example function, In mathematics, a function associates one quantity, the a …   Wikipedia

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • Finite state machine — A finite state machine (FSM) or finite state automaton (plural: automata ) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an… …   Wikipedia

  • Laws of Form — (hereinafter LoF ) is a book by G. Spencer Brown, published in 1969, that straddles the boundary between mathematics and of philosophy. LoF describes three distinct logical systems: * The primary arithmetic (described in Chapter 4), whose models… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”