ネットサービスの開発に役立ちそうな話題を中心にお届けします。
F.Ko-Jiの「一秒後は未来」 > 日記 > Y コンビネータについて調べてみた
2008年01月26日 17:29
1473日前に投稿

Y コンビネータについて調べてみた

  • ... PV
  • このエントリーをはてなブックマークに追加

スポンサード リンク

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
» λ計算とは - はてなダイアリー

スポンサード リンク

Written by
関連エントリーはこちら
お探しの情報が見つからない場合はサイト内検索もお試しください。
Meity.jp - 「DM送りたいのでフォローしてください」とかめんどくさくないですか？


トラックバック

このエントリーのトラックバックURL:

日記

English version

2008/01/26 17:29:48 by F.Ko-Ji
コメント (0) トラックバック (0) 日記

前のエントリー: « 宇多田ヒカルが紹介していたスワロフスキーのクリスベア(クマのオブジェ)
次のエントリー: やっぱり動画はみんなで見たほうが数倍面白い(動画人JAPANイベント) »

コピペにご利用ください。

タイトル:

URL:

リンク用HTMLタグ: