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

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

Problem 13 Owls

Owl Oは以下の条件を満たす。

1
Oxy = y(xy)

OをB,C,Wを用いて表せ。実際QとWで表すことができる

解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Oxy = y(xy)
= Byxy
= CBxyy
= W(CBx)y
= BW(CB)xy

よってO=BW(CB)である

Oxy = y(xy)
= Qxyy
= W(Qx)y
= QQWxy

よってQとWを使うとO=QQWである

Problem 14

賢人鳥はOとLから導くことができる。
まだ良いのはTuring birdをOとLから導ける。
どうやるか

解

1
2
3
4
U=y(xxy)
=O(xx)y
=LOxy
よってU=LOであり賢人鳥はLO(LO)である

Problem 15

mockingbirdがOとIから導けることを示せ

解

1
2
OI=y(Iy)=yy
よってM=OIである

Problem 16

OがSとIから導けることを示せ

解

1
2
SIxy=Iy(xy)=y(xy)
よってO=SIである

Problem 17

次の問題への準備として
xがyを好きならば
xはxyを好きなことを示せ

解

1
2
3
4
5
xがyを好きならば
xy = y
xがyを好きかつy = xyより
x(xy) = xy
よってxはxyが好き