不動点オペレータ

Scheme

どうやら、Yコンビネータという名前はあんまり一般的な名前ではなく、不動点コンビネータやら、不動点オペレータというのが一般的な名前らしい。

鉄は熱いうちに打てって言葉があるので、勢いで行く事にする。

英語だけど、Fixed point combinator - Wikipedia, the free encyclopediaの前半部分を読んで行きます。

不動点

数学でいう,不動点ってのは

不動点 - Wikipedia

f(x) = xになるような点。

つまり、gnuplotすると、

gnuplot> plot x

と交差するような点の事を不動点という。つまり、入力と出力の結果が変わらない点って事。

一般的な式にする

苦労して(遊びすぎて)手に入れた式。Yコンビネータの定義。引数をちょっと変形。

(define Y
  (lambda (f)
    ((lambda (x)
       (f (lambda a (apply (x x) a))))
     (lambda (x)
       (f (lambda a (apply (x x) a)))))))


一般的な式にすると、

Y = λf.(λx.f(λa.(x x) a)) (λx.f(λa.(x x) a))

読みにくいけど、

λ 引数 . 関数本体

という形。

λ演算では、applyの所は考えないとして、

Y = λf.(λx.f(x x)) (λx.f(x x))

こうおく。

xが、ズンズン評価されてしまって、無限ループに陥るので、実行は出来ない。数学はイイナァ。

変形して遊ぶ

Y gと引数を当てる。

Y g = (λf.(λx.f(x x)) (λx.f(x x))) g

まんまっすな。

fにgを代入する。β変換。

Y g = (λx.g(x x)) (λx.g(x x))   [1]

左側のxをyに変える。α変換。

Y g = (λy.g(y y)) (λx.g(x x))

左側のyに、右側のyを代入する。β変換。

Y g = g ((λx.g(x x)) (λx.g(x x)))

となって、[1]の式を適用すると、

Y g = g (Y g)

Y g = g (Y g)が、証明出来ました。

入力と出力はおんなじものが出てくるので、Yを不動点オペレータというらしい。

まとめ

英語は殆んど読んでません。ゴメンナサイ。ゴメンナサイ。いた、いた、石なげちゃ・・・

  • α変換は引数の名前を変えること。
  • β変換は代入の事。

残念ながら、Y無限ループではどんどんgを生み出しちゃうので、gの中を評価し次の(Y g)を生み出すようにする。

なんだスゲー簡単じゃん!!