Combinatory logic

:This article is about a topic in mathematical logic and theoretical computer science, and is not to be confused with combinatorial logic, a topic in electronics.

(y x)

The motivation here is that B and C are limited versions of S.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Whereas S takes a value and substitutes it into both the applicand and

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

its argument before performing the application, C performs the

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

substitution only in the applicand, and B only in the argument.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Reverse conversion

The conversion L from combinatorial terms to lambda terms is

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

trivial:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

L = λx.x

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

L = λx.λy.x

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

L = λx.λy.λz.(x z y)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

L = λx.λy.λz.(x (y z))

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

L = λx.λy.λz.(x z (y z))

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

L = (L L)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Note, however, that this transformation is not the inverse

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

transformation of any of the versions of T that we have seen.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Undecidability of combinatorial calculus

It is undecidable whether a general combinatory term has a normal

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

form; whether two combinatory terms are equivalent, etc. This is

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

equivalent to the undecidability of the corresponding problems for

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

lambda terms. However, a direct proof is as follows:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

First, observe that the term

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Ω = (S I I (S I I))

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

has no normal form, because it reduces to itself after three steps, as

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

follows:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

(S I I (S I I))

~ ~ ~ ~ ~ ~ ~ ~ ~ ~