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

Problem 10 Currys Sage Bird

B,S,Wから賢人鳥を導けることを示せ。
注：これはProblem 5への別解になる

解

SLLは賢人鳥だったので
SLL = WSL = WS(BWB)が解

THE TURING BIRD

Turing bird Uは以下の式を満たす。

Uxy = y(xxy)

この鳥はアラン・チューリングによって1937年に発見された

Problem 11 Finding a Turing Bird

B,M,Tとそれらを使って構成できる鳥を使ってUを求めよ

解

B,M,Tのいる森にはW,L,Qもいる
Uxy = y(xxy)
=Q(xx)yy
=LQxyy
=W(LQx)y
=BW(LQ)xy

よってU = BW(LQ)である

Problem 12 Turing Birds and Sage Birds

turing birdの目覚ましい特徴の一つは、UのみでSage Birdを構成できることにある。
どうやるか

解

任意のxとyについて
Uxy = y(xxy)
UUy = y(UUy)
よってUUはSage Birdである