Instead, it is important in the mathematical theory of algorithms because it is an extremely simple Turing complete language.
Informally, and using programming language jargon, a tree (xy) can be thought of as a function x applied to an argument y.
From these definitions it can be shown that SKI calculus is not the minimum system that can fully perform the computations of lambda calculus, as all occurrences of I in any expression can be replaced by (SKK) or (SKS) or (SK x) for any x, and the resulting expression will yield the same result.
One interesting property of it is that its self-application is irreducible: Or, using the equation as its definition directly, we immediately get U U = U U.
α will have to employ some kind of conditional to stop at some "base case" and not make the recursive call then, to avoid divergence.
This becomes much shorter with the use of the B,C,W combinators, as the equivalent And with a pseudo-Haskell syntax it becomes the exceptionally short Y = U .
And in general, S(K(Sf))K is equivalent to Cf, for any f. SKI combinator calculus can also implement Boolean logic in the form of an if-then-else structure.
The first works just like one of our basic combinators: The second is also fairly simple: Once true and false are defined, all Boolean logic can be implemented in terms of if-then-else structures.
Boolean NOT (which returns the opposite of a given Boolean) works the same as the if-then-else structure, with F and T as the second and third values, so it can be implemented as a postfix operation: If this is put in an if-then-else structure, it can be shown that this has the expected result Boolean OR (which returns T if either of the two Boolean values surrounding it is T) works the same as an if-then-else structure with T as the second value, so it can be implemented as an infix operation: If this is put in an if-then-else structure, it can be shown that this has the expected result: Boolean AND (which returns T if both of the two Boolean values surrounding it are T) works the same as an if-then-else structure with F as the third value, so it can be implemented as a postfix operation: If this is put in an if-then-else structure, it can be shown that this has the expected result: Because this defines T, F, NOT (as a postfix operator), OR (as an infix operator), and AND (as a postfix operator) in terms of SKI notation, this proves that the SKI system can fully express Boolean logic.
As the SKI calculus is complete, it is also possible to express NOT, OR and AND as prefix operators: The combinators K and S correspond to two well-known axioms of sentential logic: Function application corresponds to the rule modus ponens: The axioms AK and AS, and the rule MP are complete for the implicational fragment of intuitionistic logic.