コンビネータ論理►to mock a mockingbird

to mock a mockingbirdを読む(43)18章

The Master Forest

Craigはマスターフォレストの入り口にたどり着いた。
入り口には「エリートのみ入ってよい」という看板があった。
また、「お前はエリートか」と問いかけてくるガーディアンが道を遮った。
「それはエリートの定義による」とCraigは答え、ガーディアンは
「鳥類学者グリフィンの定義によると、入りたいと望むものがエリート」だという。
「もちろん(入りたい)」とCraigは答えマスターフォレストに入るのであった。
鳥類学者グリフィンの家にたどり着くとCraigは歓迎された。
「この森にはStarlingとKestrel、それからその2種から派生する鳥だけが生息している」
とグリフィンは答えた。
bluebird,dove,blackbird,eagle,bunting,dickcissel,becard,dovekie,bald eagle,warbler,
cardinal,identity bird,thrush,robin,finch,vireo,queer bird,quixotic bird,quizzical bird,
quirky bird,quacky bird,mockingbird,lark,sage bird,Turing bird,owl
これらの鳥を知っているかとグリフィンが聞くと「全て知っている」とCraigは答えた。
Craigは、これらの鳥はB,T,M,Iの4つの鳥から全て派生できることを知っていたが
グリフィン曰く、B,T,M,IもSとKから生成できると答えた。
「SとKからは任意のcombinatorial birdが派生できる」とグリフィンは言った

Problem 1

Identity birdをSとKを用いて表せ

解

1
2
3
4
SKSx=Kx(Sx)=x
SKKx=Kx(Kx)=x
よってI=SKS=SKKである
なお、一般的な慣習としてはSKKが使われる

Problem 2

MockingbirdをSとIを用いて表せ

解

1
2
SIIx=Ix(Ix)=xx=Mx
よってM=SIIである

Problem 3

S,K,Iを用いてThrushを表せ

ヒント
まず、次の2条件を満たすX1を求める
1.X1はS,K,Iと変数xからなり、変数yはX1に含まれない
2.X1y=yxが成り立つ
次に
X2x=X1となるようなS,K,IからなるX2を求める
X2xy=X1y=yxとなるのでX2が求めるthrushとなる

解

1
2
3
4
5
6
7
8
9
10
11
12
13
SI(Kx)y=Iy(Kx)y=yx
よってX1=SI(Kx)である。
K(SI)x=SI
Kx = Kx
なので
S(K(SI))Kx=(K(SI)x)(Kx)=SI(Kx)
よってX2=S(K(SI))KがThrushである。
ここは本ではT=S(K(SI))となっているが誤りと思われる
S(K(SI))Kxy=K(SI)x)(Kx)y
=SI(Kx)y
=Iy(Kxy)
=yx
となりチェックも通る

Problem 4

S,K,Iを用いてBluebirdを表せ

ヒント
まず、X1z=x(yz)となるX1(S,K,I,x,yからなりzは含まない)を見つける。
次に、X2y=X1が成り立つようなX2(S,K,I,xからなりy,zは含まない)を見つける。
次に、X3x=X2となるX3(SKIのみからなる)を見つける。これがbluebirdである。

解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Sに2つ作用させるものを考える。(それぞれにzを作用させる)
Kxz=x
yz=yz
なのでS(Kx)yz=Kxz(yz)=x(yz)
よってX1=S(Kx)yである。

これは既にX2y=S(Kx)yという形をしているので
X2=S(Kx)である

最後にX3x=X2となるものを考える。
Sに二つ作用させるものを考える(それぞれにxを作用させる)
これがそれぞれSとKxとなるようになるものを考えれば良い。
KSx=S
Kx=Kx
よってS(KS)Kx=KSx(Kx)=S(Kx)
つまりB=S(KS)Kである