deniok: (typed lambda)
[personal profile] deniok
Придумал задачку по лямбда исчислению.

Общеизвестен лямбда-терм, не имеющий нормальной формы
(\x.xx)(\x.xx)
Этот терм обладает следующим свойством: он воспроизводит сам себя при каждой бета-редукции, ведя себя по отношению к ней как экспонента по отношению к дифференцированию.

А теперь задача: написать не имеющий нормальной формы терм, который бы вел себя как e^(-x). То есть при первой бета-редукции он должен превращаться во что-то другое, а при следующей возвращаться к исходному виду. Моя версия такого терма (flipflop) под катом белым цветом


flip = \xyz.xyzz
flop = \xyz.yxxz

flipflop = flip flop flop flip ~> -- первая редукция
flop flop flip flip            ~> -- вторая редукция
flip flop flop flip            = flipflop



Может кто придумает попроще?

UPD: Эх, а у меня-то решение неправильное :) (Потому что у меня аж шесть шагов) Правильное - у [livejournal.com profile] lomeo в комментах.
This account has disabled anonymous posting.
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting

Profile

deniok: (Default)
deniok

February 2022

S M T W T F S
  12345
6789101112
13141516171819
20212223 242526
2728     

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 6th, 2025 02:19 am
Powered by Dreamwidth Studios