人気ブログランキング | 話題のタグを見る

関数の自己適用

Y - コンビネータのλ式は次のようになる。

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

このコードには不可解な点が多いが、先ず目につくのは (x x) という関数の自己適用だ。関数 x をそれ自身の x に適用させている。Y-コンビネータはさらにこの関数の自己適用でできた関数を利用して、(f (x x)) (f (x x)) とさらに2重の関数の自己適用を行っている。おそらく、これが、Y-コンビネータの無名関数で再帰的定義の関数をつくるという離れ業の原因だろう。

そこで、まず、最も単純な (x x) という形の関数の自己適用について考えてみた。この形の関数の自己適用が行われたときに x について必要な条件はなんだろうか。まず、x は関数 x を引数として取るので高階関数でなくてはならない。x に 2 を代入して (2 2) としてもこれは動作しない。

それでは x = λy.(y*2) の場合はどうだろうか。この場合 (x x) = ((λy.(y*2)) (λy.(y*2))) となるが、これも動作しない。λy.(y*2) は数値の引数をとり、数値を戻り値として返す関数だ。別の言い方をすると、この関数の domain は数値の集合で、codomain も数値の集合である。従って λy.(y*2) は関数である λy.(y*2) を引数にとることはできない。

こんどは x = id の場合を考えてみる。id x 関数は次のように定義され、引数 y をそのまま返す関数だ。

id y = y

この関数 id は (id id) のように関数の自己適用ができるだろうか。これは可能だ。id は引数 id をそのまま帰すので (id id) = id となる。これは次のように Haskell でも試してみることができる。

Prelude> let id x = x
Prelude> id 2
2
Prelude> ((id id) 2)
2
Prelude> ((id (id id)) 2)
2
Prelude> ((id (id (id id))) 2)
2

(id id) = id なので (id (id id)) や (id (id (id id))) のようなものも全て id と等しくなる。つまり、(x x) という関数の自己適用は、

(x x) = (x (x x)) = (x (x (x x)) = (x(x(x(.... (x x)....))))

と無限に展開するラムダ式を発生させることができる。まるで合わせ鏡のように、(x x) という簡潔な表現の中に無限を閉じ込めることができるのだ。x が関数の場合、x のdomain は関数の集合で、x の codomain も関数の集合なので、この展開は無現に続けることができる。

そこで改めて Y-コンビネータ (f (x x)) (f (x x)) を展開してみよう。

(f (x x)) (f (x x))
= (f ((f (x x)) (f (x x)))
= (f (f ((f (x x)) (f (x x))))
= (f (f (f (f .... ((f (x x)) (f (x x))) .... ))))

やはり、この式が無限に展開できることが分かる。これは f (x x) のように f が合わせ鏡の関数を引数に取るために、それを展開すると f ((f (x x)) (f (x x))) となり、展開された f の引数が ((f (x x)) (f (x x)) のように元のλ式になってしまうからだ。

Y-コンビネータの場合、任意の関数 g を上の f にあてはめることができるので、つぎの等式が成立する

Y g = g (Yg)

したがって g に階乗を求める関数をとると、

(Y g) 5 = 5 * (g (Y g) 4)) = 5 * 4 * (g (Y g) 3) = ...

となって遅延評価の関数言語であれば、階乗の計算ができることになる。それだけではなく、g に任意の再帰関数をとれば、任意の再帰関数の定義が Y g でできることが分かる。

Haskell では遅延評価なのでつぎのように簡単に階乗を計算する無名関数を記述することができる。

Prelude> let y x = x (y x)
Prelude> (y (\f n -> if (n == 1) then 1 else n*(f (n-1)))) 5
120

このように関数が first-order のデータであるような言語では、高階関数の自己適用により合わせ鏡のような関数を記述でき、そのなかに無限の操作を導入することができる。ただし、その場合無限の展開が終わらない場合も出てくるので、絶対に停止するプログラムだけを作ることはできなくなる。

ラッセルのパラドックスのメカニズムも自己言及が原因なので、このような合わせ鏡のメカニズムが関係している可能性がある。素朴集合論の世界は、プログラム記述可能な世界と同じものなのだろう。素朴集合論の世界でも無限を全て捉えたと考えてくると矛盾がでてくるが、プログラムの世界も無限の全体を捉えることはできない。しかし、どちらも無限にそれを展開していくことができるという可能無限な世界なのだ。

by tnomura9 | 2017-11-19 07:05 | ラッセルのパラドックス | Comments(0)
<< ラッセルのパラドックスとY-コ... Z - コンビネータ >>