F.Ko-Jiの「一秒後は未来」

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

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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

著者について

fkoji

F.Ko-Ji

Webエンジニアやってます。最近は ドットインストール の開発がお仕事です。その傍ら、個人で Meity電車遅延なう梅酒.in#グラドル自画撮り部 の部室といったネットサービスを開発・運営してます。梅酒と草野球とリアル脱出ゲームが好きです。

» 詳しいプロフィールや運営サービスの一覧など