2008
01
26
Y コンビネータについて調べてみた
スポンサード リンク
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
» λ計算とは - はてなダイアリー
前のエントリー: « 宇多田ヒカルが紹介していたスワロフスキーのクリスベア(クマのオブジェ)
次のエントリー: やっぱり動画はみんなで見たほうが数倍面白い(動画人JAPANイベント) »
トラックバック
このエントリーのトラックバックURL:
このブログをRSSリーダーで簡単購読
タイトル:
URL:
リンク用HTMLタグ:
powered by Google Chart API
