Problem 1

Mockingbird,Bluebird,Robinを用いて賢人鳥(sage bird)を導出せよ。
これは5文字の式からなる

解

1
2
3
4
5

11章のproblem 2より
任意の鳥xについてΘx = M(BxM)とおける。
M(BxM)=M(RMBx)
=BM(RMB)x
よってΘ=BM(RMB)となる

Problem 2

B,C,Mからなる5文字の賢人鳥を見つけよ

解

1
2
3
4
5

BxM=CBMxであるので
M(BxM)=M(CBMx)
=BM(CBM)x

よってBM(CBM)はsage birdである

Problem 3

もっとシンプルな賢人鳥の式はM,B,Lを用いて表せる
これを見つけよ

解

1
2
3
4

9章のproblem 25でxはLx(Lx)が好きだということを見た。
Lx(Lx)=M(Lx)=BMLx
よってBMLはsage birdである。
CBM=RMB=Lであるので、problem 1,2の答えを再度確かめることができる

Problem 4

M,B,Wを用いて賢人鳥を導出せよ

解

1
2

一つ前の章のProblem 3よりBWBはLarkであるので
BM(BWB)がSage birdである

Problem 5

賢人鳥をB,C,Wから導くのはより難しいが、導けるか

解

一旦保留し、Problem 7の解答で答える

Problem 6

Q,L,Wを用いて賢人鳥を求めよ

解

1
2
3
4
5
6

Lx(Lx)
=QL(Lx)x
=QL(QL)xx
=W(QL(QL))x

よってW(QL(QL))はsage bird

Problem 7

再度Problem 5を解け

解

1
2
3
4
5
6
7
8

Q=CBであるので(原著はQ=BCと誤植がある)
前問の結果より
W(QL(QL))
=W(CBL(CBL))
=W(B(CBL)L)
ここでL=BWBであるので
=W(B(CB(BWB))(BWB))
これがSage Birdである

A Gallery of Sage Birds

order 1の鳥とは鳥Aについて、Axがxのみで表せることをいう。
mockingbirdMx = xxやidentity bird I x = xなどがこれに当たる。
これまでに出てきたコンビネータの中では、この2つだけがorder 1に該当する。
もちろんorder1の鳥は無数にあり、例えばAx = x(xx)やAx=(x(xx))((xxx)x)といったものを考えることができる。

order 2の鳥とは鳥Aについて、Axyがxとyのみから表せることをいう。
order 2の鳥としては、Thrush, Lark, Warblerなどが挙げられる。

同様にorder 3の鳥とは鳥AについてAxyzがx,y,zのみで表せることを言う。
ここまでに遭遇した鳥の多くはorder 3である。
B,C,R,F,Vに加えてQ,Q1,Q2,Q3,Q4はorder 3となる。

同様に考えてorder 4,5,6,7,8などを考えることができる。
Doveはorder 4,Bald Eagleはorder 7である。

オーダーを持たない鳥もいる。例えばTIx=xIでIを消すことができないのでTIはオーダーを持たない。
TIxy=xIy TIxyz=xIyzと変数を増やしてもIが消せないため、オーダーを持てない。
何らかのオーダーを持つ鳥はproper combinatorial bird,またはもっと短くproper birdと呼ぶ。

combinatorial birdとは、proper birdを用いて表現できる鳥を言う。
combinatorial birdはproperとは限らない。
TIはcombinatorial birdだがproperではない。
一方ITはproperである。IT = Tであるため。

SOME SAGE BIRDS

賢人鳥(sage bird)Θとは、任意の鳥xについて以下を満たす鳥を言う。

1
2

x(Θx)=Θx
(xはΘxが好き)

賢人鳥はproper birdではない。
しかしproper birdを使って賢人鳥を表すことはできる。
10章では具体的な賢人鳥は求めずにその存在を示したが、
ここからはあるproper birdの元で賢人鳥を求めていく

Exercise 4

psi bird Ψは以下の条件を満たす

1

Ψxyzw = x(yz)(yw)

psi birdはコンビネータ論理ではスタンダードなものである。
B,C,Wからpsi birdが導出できることを示せ

ヒント：H*=BHとしてH*とD2から簡単に導出できる。
D2 x y z w v = x (y z) (w v)であった

解

1
2
3
4
5

psi x y z w = x (yz)(yw)
= D2 x y z y w
= H* D2 x y z w

よってΨ=H* D2である

Exercise 5

ΨがΦとBとKから導けるのは奇妙な事実である。
ここでは問題を二つに分ける。
a.以下の条件を満たすΓがΦとBから導けることを示せ

1

Γxyzwv = y(zw)(xywv)

b.ΦがΓとKから導出できることを示せ

解

1
2
3
4

a.
自分では解けませんでしたが解答は
Γ=Φ(Φ(ΦB))B
b.Φ=Γ(KK)

Exercise 6

Sと、BとTから導出した鳥を用いて
以下の条件を満たすS’を導出せよ

1

S' xyz = yz(xz)

解

1
2
3
4
5

S' x y z = y z (x z)
= Syxz
= CSxyz

よってS'=CSである

Exercise 7

CQ^WがStarlingであるようなQのみから導出できるQ^が存在する。
6文字からなるのだがこれを導出せよ

解

1
2

これも自力では解けませんでした
解はQ^=Q(QQ(QQ))Q

Problem 16

MがTとSから導出できることを証明せよ

解

1
2

STがWarblerであったので
WT=STTがmockingbirdである

Exercise 1 modeled on Church’s derivation of W

a.BとTを用いて以下の条件を満たすG1を導出せよ

1

G1 x y z w v = xyv(zw)

b.G1とMを用いて以下の条件を満たすG2を導出せよ

1

G2 x y z w = xw(xw)(yz)

c.B,T,Iを用いて以下の条件部ぉ満たすI2を導出せよ

1

任意の鳥xについてI2x = x I I

d.任意の鳥xについてI2(Fx)=xであることを示せ。Fはfinchである

e.G2F(QI2)がwarblerであることを示せ。QはQueer birdである

解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

a.G x y z w = x w (y z)であった
BG x y z w v =
G (x y) z w v = x y v(z w)
よってG2=BGである

b.G1 x y z w v = x y v (z w)
G2 x y z w = xw(xw)(yz)
=M2 x w (yz)
=G1 M2 x y z w v
よってG2 = G1 M2 = G1(BM)である

c.I2x = x I I
= T I (x I)
= T I (T I x)
=B(T I)(T I) x

よってI2 = B(T I)(T I)である。

d.I2 (F x) = F x I I
= I I x
= I x
= x
よって目的の式が成り立つ

e.
G2F(QI2) x y
= Fy(Fy)(Qi2x)
=(Qi2x)(Fy)y
=x(i2 (Fy))y
=x y y(前問の結果より)
よって題意を満たす

Exercise 2 the standard starling

B(B(BW)C)(BB)がstarlingであることを示せ

解

1
2
3
4
5
6
7

s x y z = x z ( y z)
s x y z = (b b) x z y z
s x y z = (b c) (b b) x y z z
s x y z = (b(b(b w))) (b c) (b b) x y z
s x y z = b(b(b w)c)(b b) x y z

よって与式はstarlingである

Exercise 3

phoenix Φは以下の条件を満たす。

1

Φx y z w = x (y w)(z w)

phoenixはコンビネータ論理ではスタンダードなものである。
phoenixをSとBから導出せよ

解

1
2
3
4
5

Φ x y z w = x (y w)(z w)
=B x y w (z w)
= B (B S) B x y z w

よってΦ=B(BS)Bである

Problem 12 Starlings

Starling Sは以下の条件を満たす

1

S x y z = x z ( y z)

StarlingはB,T,Mから導ける。
さらにB,C,Wを用いるともっと簡単に導ける。
これは7文字だが、6文字の導出もある。
Goldfinch G(G x y z w = x w(y z))を用いてB,W,Gを使っても導ける。
どうやるか

解

1
2
3
4

S x y z = x z (y z)
=Gxyzz
=B(BW)Gxyz
よってS = B(BW)G=B(BW)(BBC)

The Starling In Action

StarlingをB,C,Wで導けることは見た。
さらにWをB,C,Sから導くこともできる。
事実WはCとSから(あるいはRとSから)導くことができる。
WはTとSからも導くことができる

Problem 13 Hummingbird Revisited

Hummingbird HはB,C,Wから導けることは前に見た。
ではHをSとCから、あるいはもっとシンプルにSとRから導けるか

解

1
2
3
4

H x y z = x y z y
=R y (xy) z
=S R x y z
よってH=SRである

Problem 14

WarblerをSとRから導け。
またSとCから導け

B,C,Sから導ける鳥のクラスはB,C,Wから導ける鳥のクラスと一致する。
なぜならSはB,C,Wから導け、WはCとSから導けるからである。

解

1
2
3
4
5
6

Problem11より
W = R(HR)R
H=SRであったので
W = R(SRR)R
= C(SRR)
= C(S(CC)(CC))

Problem 15

WはSとCから導出可能、CばBとTから導出可能。
よってWはS,B,Tから導出可能。
しかし、WはSとTから導出可能であるがどうやって導出すればよいか

解

1
2
3
4

W x y = x y y
= Ty(xy)
= STxy
よってW=STである

Problem 8

WはB,T,Mから導出できることを見た。
ではMはB,T,Wから導出できるか

解

1
2
3
4

M x = x x
= T x x
= W T x
よってM=WTである

Problem 9 Two Relatives of W

以下の条件を満たすW*,W**をB,T,Mから導け。

1
2

W* x y z = x y z z
W** x y z w = x y z w w

解

1
2
3

W* = BW
W** = B(BW)
である

Problem 10 Warblers and Hummingbirds

Hummingbird Hは以下の条件を満たす。

1

H x y z = x y z y

HをB,C,Wを用いて表せ(つまりはB,T,Mでも表せる)

解

1
2
3
4

H x y z = x y z y
=C* x y y z
=W* C* x y z
よってH=W* C*=BW(BC)である

Problem 11 Hummingbirds and Warblers

WarblerはB,C,Hからも導くことができる。
実際CとHから導ける。さらにシンプルにはRとHから導ける。
どうやるか

解

1
2
3
4

W' x y = yxx
= Rxyx
= HR xy
W = CW' = C(HR) = R(HR)Rである

Warblers

論理学者アロンゾ・チャーチは、B,T,M,Iからなる鳥のクラスに興味を持った。
1941年、チャーチはWarblerをB,T,M,Iであらわした。
これは醜く、独創的で24文字と13個のペアの括弧からなるものだった。
論理学者J.Barkley RosserはB,T,Mのみを使用し10文字からなるwarblerの表現を発見した。
B,C,Mを用いればさらにシンプルに表現が可能である。

Problem 5 The Bird W’

converse warbler W’は以下の条件を満たす。

1

W' x y = y x x

奇妙なことにW’はWよりも簡単に導ける。
B,R,Mを用いることでそれは導出できるが、どうやれば良いか

解

1
2
3
4
5
6
7
8

W' x y = y x x
= R x y x
= R x (R x) y
= M2 R x y

よってW'=M2Rである
M2=BMであったのでW'=BMR=BM(BBT)である
別解としてB(BMB)Tがある

Problem 6 The Warbler

もうW’があるのでWはシンプルに導ける。
事実、WはB,R,C,Mを使って4文字の式として導出できる。
どうやればよいか

解

1
2

CW'xy = W'yx = xyy
よってCW=C(BMR)はwarblerである

Problem 7

WをB,T,Mで表せ
10文字の式で表せるが、そのような式は2つある。

解

1
2
3
4
5
6
7
8

前章のproblem 22よりCx = B(Tx)Rであるので
B(TW')Rはwarblerである。
W'=BM(BBT),R=BBTを用いると
W=B(T(BM(BBT)))(BBT)
である。
W=B(BMB)Tを用いた場合は
W=B(T(B(BMB)T))(BBT)
である。

Mockingbirds,Warblers,and Starlings

Mockingbirdはduplicative effect(重複する効果)を持つ。
それは変数の繰り返しを引き起こす。
この効果はLarkやWarblerも持つ。
BとTから導出できる鳥にこのduplicative effectをもつものはいない。
そのためmockingbirdは彼らとは非常に独立した鳥である。

Problem 1 The Bird M2

double mockingbird M2は以下の条件を満たす。

1

M2 x y = xy(xy)

この鳥をBとMから導出せよ

解

1
2
3
4

M2 x y = xy(xy)
=M(xy)
=BMxy
よってM2=BMである

Problem 2 Larks

Lark LはLxy = x(yy)を満たすのであった。
LはB,T,Mから導出できる。
B,C,MまたはB,R,Mから導出することができるがどうやるか

解

1
2
3
4
5
6
7
8

L x y = x ( y y)
=x(My)
=BxMy
=CBMxy
あるいは
=RMBxy
よってL=CBM=RMBである
B,T,Mを使うとRMB=BBTMB=B(TM)Bとなる

Problem 3

Larkはbluebirdとwarblerからも導ける。
これを導け。
実際この事実はむしろ重要である。

解

1
2
3
4

L x y = x (y y)
=B x y y
= (BW) B x y
よってL=BWBである

Problem 4

Queer BirdとMockingbirdからもLarkは導ける。
どうやるか

解

1
2
3
4
5

L x y = x (y y)
=x (M y)
=Q M x y

よってL=QMである

Problem 43 an Old Proverb

あることわざがある。
曰く、「cardinalがいたら、quacky birdなしにはquirky birdを持つことができないし、quirky birdなしにquacky birdを持つことができない」
この諺が真実なのはなぜか

解

1
2
3
4
5
6

Q3 x y z = z (x y)
C Q3 x y z = Q3 y x z = z (x y) = Q4
Q4 x y z = z (y x)
C Q4 x y z = Q4 y x z = z (x y) = Q3
よってことわざが成り立つ。
Q3=BTだったのでQ4=C(BT)である(F* Bのかわりに)

Problem 44

Quacky birdはQ1とTから導出できるか

解

1
2
3
4

Q4 x y z = z (y x)
Q1 T x y z = T (y x) z = z (y x) = Q4
よってQ1 Tと導出できる
Q1はBCBなのでQ4=Q1T=BCBT=C(BT)と前問の結果が導ける

Problem 45 An Interesting Fact About the Queer Bird Q

以前みたようにQueer Bird QはBとTから導ける。
では、BをQとTから導けるか

解

1
2
3
4
5
6

B x y z = x (y z)
Q y x z = x (y z)
T x (Q y) z = x (y z)
Q Q (Tx)yz = x (y z)
Q T (Q Q) x y z = x ( y z)
よってB = QT(QQ)である

Problem 46

CardinalはBとTから導出するよりも簡単にQとTから導出できる。
4文字からなる式だが、それを見つけよ

解

1
2
3
4
5
6

C x y z = x z y
T y (x z) = x z y
Q x (Ty)z = x  zy
Q T (Q x) y z = x z y
Q Q (Q T) x y z = x z y
よってQQ(QT)がcardinalである

Problem 47 Goldfinches

Goldfinch Gは以下の条件を満たす。

1

G x y z w = x w (y z)

GをBとTから導け

解

1
2
3
4
5

G x y z w = x w (y z)
=C x (y z) w
=B (C x) y z w
= B B C x y z w
よってG = B B Cである

Problem 38 Quixotic Birds

鳥Qにはいくらかのいとこがいる。
そのうちもっとも重要なものの一つがQuixotic Bird Q1である。
Q1は以下の条件を満たす。

1

Q1 x y z = x(z y)

Q1がBとTから導けることを示せ。
既にBとTから導いた鳥は使ってよいものとする。

解

1
2
3
4

Q1 x y z = x (z y)
B x z y = x (z y)
C* B x y z = x (z y)
よってQ1 = C*B = BCB

Problem 39 Quizzical Birds

Quizzical bird Q2は以下の条件を満たす。

1

Q2 x y z = y(z x)

Q2がBとTから導けることを示せ

解

1
2
3
4
5

Q2 x y z = y (z x)
B y z x = y (z x)
C* B y x z = y (z x)
C* C* B x y z = y (z x)
よってQ2 = C* C* B = (BC)(BC)B=C(BCB)

Problem 40

もし森にCardinalはいるがBluebirdやThrushはいないものとする。
このとき森にquixotic birdかquizzical birdがいれば
もう一方を含むことを示せ

解

1
2
3
4
5

Q1 x y z = x ( z y)
Q2 x y z = y (z x)
C Q1 x y z = y (z x) = Q2
C Q2 x y z = x ( z y ) = Q1
よってそれぞれもう一方を含む

Problem 41 Quirky Birds

Quirky Bird Q3は以下の条件を満たす。

1

Q3 x y z = z(xy)

これをBとTから導け

解

1
2
3
4
5
6
7
8

Q3 x y z = z (x y)
B z x y = z (x y)
V* B x y z = z ( x y)
よってQ3 = V*Bである
さらに
T (x y) z = z (x y)
B T x y z = z (x y)
でもあるのでQ3=BTである

Problem 42 Quacky Birds

Qの最後の親戚Quacky bird Q4は以下の条件を満たす。

1

Q4 x y z = z (y x)

これをBとTから導け

解

1
2
3
4

Q4 x y z = z (y x)
B z y x = z (y x)
F* B x y z = z (y x)
よってQ4 = F* Bである