Комбинатор Y

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

Комбинатор Y (комбинатор неподвижной точки) — один из комбинаторов в комбинаторной логике, чья комбинаторная характеристика выглядит следующим образом:

\(Y x = x (Y x)\)

Выражается в базисе S, K, I следующим образом:

\(Y \equiv S(K(SII))(S(S(KS)K)(K(SII)))\)

В λ-исчислении этот комбинатор выражается следующим образом:

\(Y \equiv \lambda f.(\lambda x.f(xx))(\lambda x.f(xx))\)