Y コンビネータについて調べてみた
2008/01/26 17:29:48
スポンサード リンク
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
» λ計算とは - はてなダイアリー
【あわせて読みたい】
- 検索エンジンロボットのクロール間隔を調整する方法(ただしGoogleを除く) [2008-04-20]
- ミリオンドリーム宝くじの当選確率をドリームジャンボ宝くじと比べると？ [2008-05-05]
- ある地点から東に⊿xメートル、北に⊿yメートル離れた地点の緯度・経度を求める方法 [2006-09-14]
- 「しょこたん☆ぶろぐ」の容量はどの程度か [2006-08-16]
前のエントリー: « 宇多田ヒカルが紹介していたスワロフスキーのクリスベア(クマのオブジェ)
次のエントリー: やっぱり動画はみんなで見たほうが数倍面白い(動画人JAPANイベント) »
トラックバック
このエントリーのトラックバックURL:
このブログをRSSリーダーで簡単購読
タイトル:
URL:
リンク用HTMLタグ:
powered by Google Chart API
