Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
SKI combinator calculus
The SKI combinator calculus is a combinatory logic system and a computational system. It can be thought of as a computer programming language, though it is not convenient for writing software.[citation needed] Instead, it is important in the mathematical theory of algorithms because it is an extremely simple Turing complete language. It can be likened to a reduced version of the untyped lambda calculus. It was introduced by Moses Schönfinkel and Haskell Curry.
All operations in lambda calculus can be encoded via abstraction elimination into the SKI calculus as binary trees whose leaves are one of the three symbols S, K, and I (called combinators).
Although the most formal representation of the objects in this system requires binary trees, for simpler typesetting they are often represented as parenthesized expressions, as a shorthand for the tree they represent. Any subtrees may be parenthesized, but often only the right-side subtrees are parenthesized, with left associativity implied for any unparenthesized applications. For example, ISK means ((IS)K). Using this notation, a tree whose left subtree is the tree KS and whose right subtree is the tree SK can be written as KS(SK). If more explicitness is desired, the implied parentheses can be included as well: ((KS)(SK)).
Informally, and using programming language jargon, a tree (xy) can be thought of as an application of the function x to an argument y. When evaluated (i.e., when the "function" is "applied" to the argument), the tree "returns a value", i.e., transforms into another tree. The "function", "argument" and the "value" are either combinators or binary trees with application nodes. If they are binary trees, they may be thought of as functions too, if needed.
The evaluation operation is defined as follows:
(x, y, and z represent expressions made from the combinators S, K, and I, and possibly variables standing for some as yet unspecified SKI expressions):
I returns its argument:
K, when applied to any argument x, yields a one-argument constant function Kx, which, when applied to any argument y, returns x:
Hub AI
SKI combinator calculus AI simulator
(@SKI combinator calculus_simulator)
SKI combinator calculus
The SKI combinator calculus is a combinatory logic system and a computational system. It can be thought of as a computer programming language, though it is not convenient for writing software.[citation needed] Instead, it is important in the mathematical theory of algorithms because it is an extremely simple Turing complete language. It can be likened to a reduced version of the untyped lambda calculus. It was introduced by Moses Schönfinkel and Haskell Curry.
All operations in lambda calculus can be encoded via abstraction elimination into the SKI calculus as binary trees whose leaves are one of the three symbols S, K, and I (called combinators).
Although the most formal representation of the objects in this system requires binary trees, for simpler typesetting they are often represented as parenthesized expressions, as a shorthand for the tree they represent. Any subtrees may be parenthesized, but often only the right-side subtrees are parenthesized, with left associativity implied for any unparenthesized applications. For example, ISK means ((IS)K). Using this notation, a tree whose left subtree is the tree KS and whose right subtree is the tree SK can be written as KS(SK). If more explicitness is desired, the implied parentheses can be included as well: ((KS)(SK)).
Informally, and using programming language jargon, a tree (xy) can be thought of as an application of the function x to an argument y. When evaluated (i.e., when the "function" is "applied" to the argument), the tree "returns a value", i.e., transforms into another tree. The "function", "argument" and the "value" are either combinators or binary trees with application nodes. If they are binary trees, they may be thought of as functions too, if needed.
The evaluation operation is defined as follows:
(x, y, and z represent expressions made from the combinators S, K, and I, and possibly variables standing for some as yet unspecified SKI expressions):
I returns its argument:
K, when applied to any argument x, yields a one-argument constant function Kx, which, when applied to any argument y, returns x: