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

[deniok]

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

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

FM = MF

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

GMN = NG(NMG)

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

Comments

[lomeo.livejournal.com]

Ну, аналогичными преобразованиями

G = Y (\f m n. n f (n m f))

[deni-ok.livejournal.com]

Браво! Ты, как обычно, лучший! На самом деле это теорема

Пусть имеется терм C=C[f,m,n,k,...] содержащий (возможно) указанные свободные переменные. Тогда для произвольных термов M, N, K, ... существует терм F, такой что

F M N K ... = C[f:=F][m:=M][n:=N][k:=K]...

Доказательство - конструктивное, конструируется

F = Y(\fmnk... -> C[f,m,n,k,...])

и доказывается, что это то, что надо :)

[lomeo.livejournal.com]

Спасибо! Я уже, когда выложил второе решение только заметил, что там всё просто конструируется.