不動点を求める関数の導出

月曜日にgrassの話題で盛り上がったときにふと思った疑問を行き帰りの電車の中とかでずっと考えている。

このエントリーでは、あえて一般的に使われる表記ではなくて、僕が一番わかりやすいと思う表記を使ってみる。つまり、「引数をそのまま返す関数I」は (\x -> x) で、「引数xをとって『どんな引数で呼ばれても必ずxを返す関数』を返す関数K」は (\x -> (\y -> x)) で、「関数fを引数xで呼ぶ(またはxに関数fを適用する？)」は f(x) と表記することにする。イコールは代入ではなく「同じ物」という意味。

ある関数fについて考える。あるxについて、 f(x) = x が成り立つとき、つまり、xに関数fを適用しても変化しないとき、「xはfの不動点」という。どんなものでもIの不動点。xはK(x)の不動点。Kの不動点は何？？

ある関数fが与えられたときに、その不動点を求めたい。ある「不動点を求める関数」Yがあって、Y(f) が f の不動点になるといいな。つまり、Y(f) = f(Y(f)) = f(f(Y(f)) = ...

どういう関数ならこの条件を満たすか？

まず I = (\x -> x) だったらどうか？ I(f) = f これじゃぜんぜん足りない。 I(f) = f(I(f)) になって欲しいわけなのでぜんぜん足りない。

じゃぁ、M = (\x -> x(x)) だったらどうか？ M(f) = f(f) ちょっと近づいた。M(f) = f(M(f)) になって欲しいんだ。中身がM(f)になって欲しいんだな。

だったら、N = (\x -> x(M(x))) ならどうだ？ N(f) = f(M(f)) だいぶゴールに近づいた。でもこれを繰り返していてもゴールにはたどり着けない感じがする。一歩飛躍が必要だ。表現力が足りない。

もう一個引数を増やしてみる。
(\x, y -> ...)という形の関数を考える。たとえば F = (\x, y -> x(y)) なら、F(f) = (\y -> f(y)) になる。

F(f) = f(F(f)) になって欲しいんだった。F(f)にもう一個何か引数を渡すと、今ならF(f)(y) = f(y) になっている。これが、F(f)(y) = f(F(f)(y))になるようなFとyがあればいいんだ。yがxの関数であれば、(\x -> F(x)(y))が求めているYになる。

F = (\x, y -> x(y)) ではどうしても話がふくらまないので、1引数の時にやったようにyをふくらませてみる。 L = (\x, y -> x(y(y)))

L(x)(y) = x(y(y))

L(x)(y) = x(L(x)(y))になってほしいんだった。お、ゴールは目前だ。上の式と見比べると、y = L(x) にするとよさそうな気配がする。

y = L(x) なら L(x)(y) = L(x)(L(x)) で、L(x)(y) = x(y(y)) = x(L(x)(L(x))) 二つを見比べる。Y = (\x -> L(x)(L(x))) とおけば Y(x) = x(Y(x)) だ！できた！

展開してみよう。L = (\x, y -> x(y(y))) だったので、L(x) = (\y -> x(y(y)))。
Y = (\x -> L(x)(L(x))) = (\x -> (\y -> x(y(y)))((\y -> x(y(y)))))

Yコンビネータができたはずだけど、これがどう再帰呼び出しにつながっていくのかがわからない。第1引数が関数で第2引数が整数な関数(\f, n -> ...)をYコンビネータにつっこんで再帰呼び出しとかしている例はよく見かけるけど、それじゃy(y)のところで整数がcallableじゃないのでエラーになるよね。まだいくつかピースが足りていない。明日も電車で考える。

• • • • -

困ったときのPython頼み。Yが上の定義で、Y2が再帰呼び出しにYコンビネータが使えるという文脈でよく出てくるコードと、それを上に出てきたMコンビネータを使ってシンプルに書いたもの。

>>> Y = (lambda x: (lambda y: x(y(y)))(lambda y: x(y(y))))

>>> Y2 = (lambda f:((lambda g: f(lambda x: g(g)(x)))
	          (lambda g: f(lambda x: g(g)(x)))))
>>> Y2(lambda f: lambda n: n and n * f(n - 1) or 1)
<function <lambda> at 0x00DBEAB0>
>>> _(5)
120

>>> M = lambda x: x(x)
>>> Y2 = (lambda f: M(lambda g: f(lambda x: g(g)(x))))
<function <lambda> at 0x00DBEAF0>
>>> _(5)
120

間にlambda xが挟まっている。これの存在意義を明日電車で考える。

>>> Y =  (lambda x: M(lambda y: x(          y(y)   )))
>>> Y2 = (lambda f: M(lambda g: f(lambda x: g(g)(x))))