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

to mock a mockingbirdを読む(19)11章

Problem 19

bluebird B, thrush T,mockinbird Mが与えられたとき、
各鳥とcommuteである鳥を求めよ

解

1
2
3
4
5
6
7
Problem 2より各鳥xはM(BxM)が好きである。
M(BTM)を考えるとTはM(BTM)が好きなので
T(M(BTM))=M(BTM)
各鳥xについて
T(M(BTM))x=M(BTM)x
左辺はx(M(BTM))となり
M(BTM)は各鳥とcommuteである

bluebirdsとthrushes

bluebird Bとthrush Tから多くの種類のpermuting birdsが導ける。
BとTからCardinalが導けることはアロンゾ・チャーチ(Alonzo Church)が1941年に発見した。
チャーチは8文字からなる導出を行ったが、もっと短くできると思われる。

Problem 20 Robins

Robin Rは以下の条件を満たす。

1
R x y z = y z x

BとTを用いてこれを導出せよ

解

1
2
3
4
R x y z = y z x
T x (yz) = y z x
DTx y z = y z x
よってR = DT = BBTである

Problem 21 Robins and Cardinals

Robin単体を使ってCardinalを導くことができる。
これを示せ。
ボーナス問題：前問とあわせることでCardinalをBとTで表せる。
しかしその場合文字数が9文字になってしまう。
1文字縮めることが加能だがどうやるか

解

1
2
3
4
5
6
7
8
9
10
11
C x y z = x z y
R y x z = x z y
R x R y z = x z y
R R R x y z = x z y
よってC = RRRであるので
C = (BBT)(BBT)(BBT)

ボーナス問題
RRR = BBTRR = B(TR)R
 = B(T(BBT))(BBT)
これがチャーチが発見した8文字の式になる