Y-Kombinator, Funktionszusammensetzung

Ich versuche Y-Kombinatoren zu verstehen. Könnten Sie bitte erklären, warum die folgenden Punkte gleichwertig sind?

(Y (f ∘ g))   
(f (Y (g ∘ f)))

(Y ist eine Festkommakombination)

Dies hängt von dem Begriff der Äquivalenz ab, den Sie verwenden.

Angenommen, wir vergleichen diese Begriffe gemäß ihrer Bezeichnungssemantik in CPO-Domänen. Bezeichne mit die Semantik der Begriffe . Somit sind Scott-kontinuierliche Funktionen. Dann haben wir, dass die Semantik von nach dem Kleene-Fixpunktsatz ist$\omega$$F,G$$f,g$$F,G$$Y(f \circ g)$

$$(1) = [\![ Y(f\circ g) ]\!] = \bigsqcup\{ \bot, F(G(\bot)),F(G(F(G(\bot)))),\ldots\}$$ wobei die Obergrenze / kleinste Obergrenze bezeichnet.$\bigsqcup$

Ebenso bekommen wir

$$(2) = [\![ f(Y(g\circ f) ]\!] = F(\bigsqcup\{ \bot, G(F(\bot)),G(F(G(F(\bot)))),\ldots\})$$

Durch Kontinuität erhalten wir

$$(2) = \bigsqcup\{ F(\bot), F(G(F(\bot))),F(G(F(G(F(\bot))))),\ldots\}$$

Man kann dann beweisen, dass indem man beobachtet, dass jedes Element einer Kette oben durch ein Element der anderen Kette begrenzt ist. In der Tat haben wir , die . Ferner ist stabilisieren , Abschluss des Beweises.$(1)=(2)$

$$\bot \sqsubseteq F(\bot), F(G(\bot)) \sqsubseteq F(G(F(\bot))), \ldots$$ $(1)\sqsubseteq(2)$ $$F(\bot) \sqsubseteq F(G(\bot)), F(G(F(\bot))) \sqsubseteq F(G(F(G(\bot)))), \ldots$$ $(2)\sqsubseteq(1)$

---

Viel weniger formal drückt der Ausdruck die unendliche Anwendung und in ähnlicher Weise drückt Es ist also ziemlich natürlich, dass das Anwenden eines einzelnen auf das zweite zum ersten führt. Der obige domänen-theoretische Beweis liefert eine formale Rechtfertigung dafür.$Y(f \circ g)$

$$f(g(f(g(\ldots))))$$ $Y(g \circ f)$ $$g(f(g(f(\ldots))))$$ $f$