Комбинаторная характеристика

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

Комбинаторная характеристика — описание (формула) комбинатора с точки зрения его функционального назначения. Представляет собой запись тождества, слева от знака (\(\equiv\)) в которой находится сигнатура комбинатора, справа — тело комбинаторной характеристики. Например, для комбинатора I комбинаторной характеристикой является формула:

\(Ix \equiv x\)

Здесь запись \(Ix\) является сигнатурой, \(x\) — телом.

Вместе с тем комбинаторы могут быть описаны не только при помощи комбинаторной характеристики. Обычным делом является выражение комбинатора через λ-терм. Так базовые комбинаторы из базиса S, K, I выражаются через λ-термы следующим образом:

\(S \equiv \lambda xyz.xz(yz)\),
\(K \equiv \lambda xy.x\),
\(I \equiv \lambda x.x\).

Такое выражение комбинаторов наталкивает на мысль, что само по себе наименование комбинатора — это идентификатор λ-терма, не более.