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

[deniok]

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

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

FM = MF

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

GMN = NG(NMG)

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

Comments

[lomeo.livejournal.com]

Первая. Во первых, берём форму

FM=(YG)M,

так как очевидно, что F - рекурсивна. Итак,

FM=(YG)M=G(YG)M
G(YG)M=MF=M(YG)
G = \a b . b a
F = Y(\a b . b a)

Вторая сложнее, сейчас подумаю.

[asviraspossible.livejournal.com]

Ну это ооочень просто с теоремой о неподвижной точки... Комменты прочитал перед тем, как написать, но когда писал ответ не читал.

1)

F M = M F
F = \x . x F = (\f x. x f) F = Y (\f x. x f) = (\f. (\x. f (x x))(\x. f (x x))) (\f x. x f)
= (\x. (\a b. b a) (x x)) (\x. (\a b. b a) (x x)) =
= (\x b. b (x x)) (\x b. b (x x))

2)

G = \m n.n G (n m G) = (\g m n. n g (n m g)) G =
(\f. (\x. f (x x))(\x. f (x x))) (\g m n. n g (n m g)) =
= (\x. (\g m n. n g (n m g)) (x x))(\x. (\g m n. n g (n m g)) (x x))
= (\x m n. n (x x) (n m (x x))) (\x m n. n (x x) (n m (x x)))

[antilamer.livejournal.com]

Я чего-то не понимаю, или это правильный ответ?
F = Y (\GM . M G)
G = Y (\FMN . N F (N M F))

Осталось только упростить. Или в этом и будет загвоздка?