lomeo: (лямбда)
Вот после долгих попыток перевести K в IBCS базис, понял, что этот базис не является полным, т.е, через него нельзя выразить любые лямбда-термы без свободных переменных.
lomeo: (лямбда)
На курсах INTUIT написано:

минимальный базис состоит всего из двух «инструкций»-комбинаторов, например, {K,S}

Выше говорится, что под выражением "минимальный" понимают мощность множества комбинаторов базиса. С большим удовольствием прочёл у Фоккера, что это далеко не так. Есть и однокомбинаторные базисы.

Фоккер приводит пример базиса, состоящего из одного комбинатора X, с помощью которого мы можем получить S и K cледующим образом:

K = XX
S = XK = X(XX)

X = λf.fS(λxyz.x)

Удивительная всё-таки наука. Подкидывает такие приятные мелочи.

(UPD) Предлагаю назвать этот комбинатор "Великим".

Profile

lomeo: (Default)
Dmitry Antonyuk

December 2015

S M T W T F S
  12345
6789101112
131415 16171819
20212223242526
2728293031  

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 23rd, 2017 03:46 am
Powered by Dreamwidth Studios