комбинаторы.
May. 30th, 2006 02:42 pmНа курсах INTUIT написано:
минимальный базис состоит всего из двух «инструкций»-комбинаторов, например, {K,S}
Выше говорится, что под выражением "минимальный" понимают мощность множества комбинаторов базиса. С большим удовольствием прочёл у Фоккера, что это далеко не так. Есть и однокомбинаторные базисы.
Фоккер приводит пример базиса, состоящего из одного комбинатора X, с помощью которого мы можем получить S и K cледующим образом:
K = XX
S = XK = X(XX)
X = λf.fS(λxyz.x)
Удивительная всё-таки наука. Подкидывает такие приятные мелочи.
(UPD) Предлагаю назвать этот комбинатор "Великим".
минимальный базис состоит всего из двух «инструкций»-комбинаторов, например, {K,S}
Выше говорится, что под выражением "минимальный" понимают мощность множества комбинаторов базиса. С большим удовольствием прочёл у Фоккера, что это далеко не так. Есть и однокомбинаторные базисы.
Фоккер приводит пример базиса, состоящего из одного комбинатора X, с помощью которого мы можем получить S и K cледующим образом:
K = XX
S = XK = X(XX)
X = λf.fS(λxyz.x)
Удивительная всё-таки наука. Подкидывает такие приятные мелочи.
(UPD) Предлагаю назвать этот комбинатор "Великим".