опять про комбинаторы

[lomeo]

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

Comments

[timlendus.livejournal.com]

Для перевода l-термов в базис I,B,C,S есть 2 правила:
1) lx.x = I
2) lx.PQ = BP(lx.Q) x не принадлежит P, x принадлежит Q
= C(lx.P)Q x принадлежит P, x не принадлежит Q
= S(lx.P)(lx.Q) x принадлежит P, x принадлежит Q
Отсюда видно что правила для ситуации, когда x не принадлежит ни P ни Q нет. Для того, чтобы проверить возможность разложения l-терма в базис I,B,C,S необходимо проверить наличие вхождения всех переменных левой части l-выражения в правую часть l-выражения. Например, lxy.x
нельзя разложить в этом базисе, т.к. нет вхождения переменной y в правую часть.
P.S. По данной тематике есть хорошие книги профессора Вольфенгагена, советую почитать.

[lomeo.livejournal.com]

Да, я собственно уже посмотрел.
Спасибо!