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^[1] and Haskell Curry.^[2]

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

^ Schönfinkel, M. (1924). "Über die Bausteine der mathematischen Logik". Mathematische Annalen. 92 (3–4): 305–316. doi:10.1007/BF01448013. S2CID 118507515. Translated by Stefan Bauer-Mengelberg as van Heijenoort, Jean, ed. (2002) [1967]. "On the building blocks of mathematical logic". A Source Book in Mathematical Logic 1879–1931. Harvard University Press. pp. 355–366. ISBN 9780674324497.
^ Curry, Haskell Brooks (1930). "Grundlagen der Kombinatorischen Logik" [Foundations of combinatorial logic]. American Journal of Mathematics (in German). 52 (3). Johns Hopkins University Press: 509–536. doi:10.2307/2370619. JSTOR 2370619.

[1] Schönfinkel, M. (1924). "Über die Bausteine der mathematischen Logik". Mathematische Annalen. 92 (3–4): 305–316. doi:10.1007/BF01448013. S2CID 118507515. Translated by Stefan Bauer-Mengelberg as van Heijenoort, Jean, ed. (2002) [1967]. "On the building blocks of mathematical logic". A Source Book in Mathematical Logic 1879–1931. Harvard University Press. pp. 355–366. ISBN 9780674324497.

[2] Curry, Haskell Brooks (1930). "Grundlagen der Kombinatorischen Logik" [Foundations of combinatorial logic]. American Journal of Mathematics (in German). 52 (3). Johns Hopkins University Press: 509–536. doi:10.2307/2370619. JSTOR 2370619.

[1]

[2]