Editing SKI combinator calculus (section)

{{Short description|Simple Turing complete logic}}
The '''SKI combinator calculus''' is a [[combinatory logic|combinatory logic system]] and a [[model of computation|computational system]]. It can be thought of as a computer programming language, though it is not convenient for writing software.{{Citation needed|date=May 2025}} Instead, it is important in the mathematical theory of [[algorithm]]s 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]]<ref>{{cite journal |first=M. |last=Schönfinkel |date=1924 |title=Über die Bausteine der mathematischen Logik |journal=Mathematische Annalen |volume=92 |issue=3–4 |pages=305–316 |doi=10.1007/BF01448013|s2cid=118507515 }} Translated by Stefan Bauer-Mengelberg as {{cite book |chapter=On the building blocks of mathematical logic |chapter-url=https://books.google.com/books?id=v4tBTBlU05sC&pg=PA355 |editor-link=Jean van Heijenoort |editor-first=Jean |editor-last=van Heijenoort |orig-year=1967 |title=A Source Book in Mathematical Logic 1879–1931 |publisher=Harvard University Press |pages=355–366 |date=2002 |isbn=9780674324497}}</ref> and [[Haskell Curry]].<ref>{{cite journal|last=Curry|first=Haskell Brooks|title=Grundlagen der Kombinatorischen Logik|journal=American Journal of Mathematics|year=1930|volume=52|issue=3|pages=509–536|authorlink=Haskell Curry|trans-title=Foundations of combinatorial logic|publisher=Johns Hopkins University Press|language=German|doi=10.2307/2370619|jstor=2370619}}</ref>

All operations in lambda calculus can be encoded via [[Combinatory logic#Completeness of the S-K basis|abstraction elimination]] into the SKI calculus as [[binary tree]]s whose leaves are one of the three symbols '''S''', '''K''', and '''I''' (called ''combinators'').