Комбинаторы

Комбинатором называется замкнутый лямбда-терм, т.е. не содержащий свободных переменных.

I ≡ λx.xIdentity
К ≡ λx y.xKonstant
S ≡ λf g x.(f x) (g x)Sharing
(совместное применение)
T ≡ λx y.x ≡ KTrue
F ≡ λx y.yFalse
Y ≡ λf.(λx.f (x x)) (λx.f (x x)) Неподвижная точка:
u Yu = u(Yu)
Ω ≡ (λx.x x) (λx.x x) Не имеет нф