Y コンビネータについて調べてみた [2008-01-26 17:29:48]

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))(λx.g(xx)))

確かに Yg と g(Yg) は一致する。とりあえずここまで。

動画人JAPAN行ってきます。

参考資料:
» ラムダ計算 - Wikipedia
» λ計算とは - はてなダイアリー