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

[deniok]

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

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

FM = MF

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

GMN = NG(NMG)

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

Comments

[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)))

[deni-ok.livejournal.com]

Ага, замечательно!