to mock a mockingbirdを読む(34)13章

Problem 8 Queer Birds and Mockingbirds

QとMを用いて賢人鳥を導け

Discussion
regular combinatorとは、proper combinatorの一種で、
その定義の左側においてもっとも左にある変数(xとする)が
右側においてももっとも左にあり、1度だけxが出現するものを言う。

具体的にはCxyz=xzyはregularである。右辺の一番左側にxが一度だけ出現しているからである。
逆にRxyz=yzxはregularではない
同様にMx=xxはregularではない。xが2回出現しているからである。
regularなコンビネータとしてはB,C,W,L,S,I,Kがあり
T,R,F,V,Qはregularではない

Problem 1,2,3,4では3つのproper combinatorから賢人鳥を導いた。
うちMだけregularでないコンビネータになる。
Problem 7では3つのregularなコンビネータから賢人鳥を導いた。
Problem 8(本問)では2つのregularでないコンビネータMとQから賢人鳥を導く。
次に2つのregularなコンビネータから賢人鳥が導けることを見ていく

解

Lx(Lx)
=M(Lx)
=QLMx
またL=QMなので
Lx(Lx)
=QLMx
=Q(QM)Mx
よってQ(QM)Mは賢人鳥である

Problem 9

StarlingとLarkから賢人鳥が導けることを示せ

解

Lx(Lx)=SLLxなので
SLLが賢人鳥である