Лямбда, которую мы потеряли

[deniok]

Пара задачек по лямбда-исчислению.

(1) Сконструируйте лямбда-терм F, такой что для любого терма M выполнялось бы

FM = MF

(2) Сконструируйте лямбда-терм G, такой что для любых термов M и N выполнялось бы

GMN = NG(NMG)

Ответы не скринятся, так что если хотите думать сами - не смотрите в комменты.

Comments

[bntr.livejournal.com]

я избегал писать символы прямо на пузырях чтобы не отпугнуть боящихся греческих букв, и вообще намеревался внедрять это в детские сады :)

надеюсь, достаточно вывода на консоль выбранного суб-терма и всего терма после редукции

регулировку скорости да, добавлю, спасибо.

интерфейс кажется довольно пошаговый: одно нажатие Enter - одна редукция. плюс возможность шагов назад.

[deni-ok.livejournal.com]

А в движке при раскраске используется классическая лямбда с альфа-конверсией или индексы de Bruijn?

[bntr.livejournal.com]

можно сказать что третий вариант: каждой новой лямбде (и связанным с ней переменным) просто назначается новый цвет из пространства цветов.

еще (но это не строго) цвета в закрытом под-терме (под-терм без свободных переменных) объединены одним тоном (hue) и отличаются только яркостью.