Комбинатор Ω

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

Комбинатор Ω — специальный комбинатор, использующийся в рамках комбинаторной логики и λ-исчисления для иллюстрации возможности бесконечных вычислений. Комбинаторная характеристика этого комбинатора выглядит следующим образом:

\(\Omega \equiv (\lambda x.xx)(\lambda x.xx)\)

Как видно при попытке редукции этого λ-выражения в результате получится оно же, так что редукция будет происходить до бесконечности. Другими словами, у этого комбинатора нет нормальной формы.

См. также[править]