3148972489

Kombinatory punktu stałego

Kombinator punktu stałego

Definicja. Kombinatorem punktu stałeao nazywamy każdy term M taki, że \/F.MF = F(MF).

Twierdzenie o punkcie stałym.

(i)    WF3X.X = FX

(ii)    Istnieje kombinator punktu stałego

Y = Xf.(Xx.f(xx))(Xx.f(xx)) taki, że YF = F(YF).

Dowód.

(i)    Niech W = Xx.F(xx) i X = WW. Wówczas X = WW = (Xx.F(xx))W F(WW) = FX

(ii)    YF = (Xf.(Xx.f(xx))(Xx.f(xx)))F

(Xx.F{xx))(Xx.F(xx))

F((Xx.F(xx))(Xx.F(xx)))

=₀ F((Xf.(Xx.f(xx))(Xx.f(xx)))F) = F{YF)

Zdzisław Spławski: Teoretyczne Podstawy Języków Progrj lia, Wykład 4. Siła wyrazu rachunku