SKI combinator calculus

The SKI combinator calculus is a <a href="/facts/Combinatory_logic/D7NNo4xT">combinatory logic system</a> and a <a href="/facts/Model_of_computation/nJr8mHSI">computational system</a>. It can be thought of as a computer programming language, though it is not convenient for writing software. Instead, it is important in the mathematical theory of <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> because it is an extremely simple <a href="/facts/Turing_complete/73goop44">Turing complete</a> language. It can be likened to a reduced version of the untyped <a href="/facts/Lambda_calculus/DaD3RuQ4">lambda calculus</a>. It was introduced by <a href="/facts/Moses_Sch%C3%B6nfinkel/7p4TkTtA">Moses Schönfinkel</a> and <a href="/facts/Haskell_Curry/PsNUI4Gn">Haskell Curry</a>.
All operations in lambda calculus can be encoded via <a href="/facts/Combinatory_logic/D7NNo4xT">abstraction elimination</a> into the SKI calculus as <a href="/facts/Binary_tree/TDV7GMpu">binary trees</a> whose leaves are one of the three symbols S, K, and I (called combinators).

SKI combinator calculus open-in-new

SKI combinator calculus