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.

(S I I (S I I))

and clearly no other reduction order can make the expression shorter.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Now, suppose N were a combinator for detecting normal forms,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

such that

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

(N x) => T, if x has a normal form

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

F, otherwise.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

(Where T and F the transformations of the conventional

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

lambda-calculus definitions of true and false, λx.λy.x and λx.λy.y.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The combinatory versions have T = K and F = (K I).)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Now let

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Z = (C (C (B N (S I I)) Ω) I)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

now consider the term (S I I Z). Does (S I I Z) have a normal

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

form? It does if and only if the following do also:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

(S I I Z)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~