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

• 
• ツイートで共有

著者について

F.Ko-Ji

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

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