to mock a mockingbirdを読む(12)10章

賢人鳥

ある鳥xについて、xへ名前を呼びかけるとxが好きな鳥を返す特別な鳥のことを賢人鳥(Sage bird)と呼ぶ。
ここでギリシャ文字のΘが賢人鳥(Sage bird)を表すことにする。
賢人鳥は時々oracle birdsとも呼ばれる。
さらにコンビネータ論理の世界ではYコンビネータとして有名である。

xはΘxが好きなので
x(Θx) = Θx

Problem1のC1とC2の元で
森に賢人鳥がいるかどうかわかるだろうか
問題は、Mockingbirdがいて、任意の鳥xについてxとMを合成したyがいる。
この時xはyyが好きであるが、xが与えられてどうやってxとMを合成したyを見つければ良いか？
なんらかの鳥Aがいてその情報を提供してくれるなら問題は解決可能になる

解

ここで出てきた鳥AはLarkに他ならない。

任意の鳥x,yについて
(Ax)y=x(My)=x(yy)
これはLarkに他ならない

これで、MとLと条件C1の元で森に賢人鳥がいるかどうかを判定する問題に帰着された。  
Problem25で任意の鳥xは(Lx)(Lx)が好きだと示したので  
xはM(Lx)=(Lx)(Lx)が好きである。
ML(x)=Θx
xはΘxが好きであるのでΘは賢人鳥に他ならない。

ここで出てきた賢人鳥はコンビネータ論理の世界では不動点コンビネータ(fixed point combinator)と呼ばれるものです。