Y コンビネータについて調べてみた - F.Ko-Jiの「一秒後は未来」Y コンビネータって何？ – IT戦記 Y コンビネータすら知らない(研究室で勉強してたかもしれないけど記憶にない)のでそこだけ調べてみた。 f=g(f) となるような関数fのことを不動点と呼ぶ 不動点を表すための演算子が不動点演算子 Y コンビネータは不動点演算子と呼ばれるものの一種 λ計算では Y = λf.(λx.f(xx))(λx.f(xx)) で定義できる。 λ計算ではYを用いると Yg が g の不動点 となる。 Y コンビネータを利用するとλ計算で再帰的な関数を定義できる Yg = g(Yg) の証明 (→はβ簡約) Yg = (λf.(λx.f(xx))(λx.f(xx)))g → (λx.g(xx))(λx.g(xx)) → g((λx.g(xx))(λx.g(xx))) g(Yg) = g((λf.(λx.f(xx))(λx.f(xx)))g) → g((λx.g(xx
