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である

to mock a mockingbirdを読む(42)17章

ゲーデルの森

Craigは次の森にやってきた。そこでこの森の鳥類学者Giuseppe Baritoniにこの森で成り立つ法則をきいた。
この森では以下の法則が成り立つ。

1
2
3
4
law 1.この森の全てのナイチンゲールは歌う
law 2.x'yはxyが歌わないときに限り、歌う
law 3.x*yはx(yy)が歌うときに限り、歌う
law 4.Nxはxがナイチンゲールであるときに限り歌う

この森ではナイチンゲールが歌うのしかきいたことがないが
ナイチンゲール以外に歌うとりはいるのかとCraigがきくと
その答えはまだ分かっていないとBaritoniは答えた。
Craigはしばらく考えたのち、ナイチンゲール以外に歌う鳥Gがいることを突き止めた。
注:文字の読みがわからないためGとしています

Problem 1

どのようにしてCraigは鳥Gがいることを突き止め、二人はどうやって
それを見つけたのか

1
2
3
4
5
6
7
8
9
10
11
12
NについてN'*を考え、これをAとする
AA、つまりN'*N'*がナイチンゲールではない歌う鳥Gであることを示す。

鳥Aは任意の鳥xについてxxがナイチンゲールでないときに限りAxが歌うという属性を持つ。これを示す。
N'*はN'(xx)が歌うときに限り歌う(law 3)。
N'(xx)はN(xx)が歌わないときに限り歌う。これはxxがナイチンゲールでないときに限り真である(law 4)
これらより、N'*はxxがナイチンゲールでないときに限り歌う。よって上の属性が示される。

xにAをあてはめると、AAはAAがナイチンゲールでないときに限り歌う。
これは、AAがナイチンゲールでなく歌うか、AAは歌わないがナイチンゲールであるかのどちらかであるが
law 1より後者は起こり得ない
よってAAはナイチンゲールではないが歌う鳥Gである。

Problem 2 A Follow-up

Gとは違う鳥でナイチンゲールではないが歌う鳥G1を見つけよ

1
2
N*'(N'*ではない)をA1とおく。
前問と類似の考察によって、A1A1=G1はナイチンゲールではないが歌う鳥G1である

Problem 3 The Bird Societies

まず、言葉の定義を行う。
鳥Aが鳥の集合Sをrepresentするとは、Sに含まれる各鳥xについて
Axが歌う鳥であり、Sに含まれない各鳥xについて
Axが歌わない鳥であることである。
言い換えると、各鳥xについて、AxはxがSのメンバーであるときにのみ歌う。

鳥の集合は、それが何かの鳥にrepresentされているときsocietyと呼ぶ。
例えばナイチンゲールの集合はsocietyを構成する。
なぜならその集合はNによってrepresentされるからである。

問題:全ての歌う鳥の集合はsocietyを形成するだろうか

1
2
3
4
5
6
7
8
9
10
11
12
13
14
まず、law3の基礎の上に、societyは歌う鳥が属するか、歌わない鳥が属さないことを証明する。
任意のsociety Sをとる。Sはなんらかの鳥Aによってrepresentされる。
ここでA*を考える。任意の鳥xについてA*xはA(xx)が歌うときのみに歌う。(law 3)
またA(xx)はxxがSのメンバーであるときにのみ歌う。なぜならAはSをrepresentするから。
よってA*xはxxがSのメンバーであるときにのみ歌う。
特にA*A*はA*A*がSのメンバーであるときにのみ歌う。
よって、歌うA*A*はSのメンバーであるか、歌わないA*A*はSに含まれないかのどちらかである

ここで、全ての歌う鳥がsocietyを作るとすると次の矛盾が導かれる。
全ての歌う鳥の集合は何らかの鳥Aによってrepresentされる。
law 2よりA'は全ての歌わない鳥の集合をrepresentする。
これより歌わない鳥の集合はsocietyを作るがこれは不可能である。
なぜなら、この集合は歌う鳥を含むか、歌わない鳥が存在してはならないからである。
よって全ての歌う鳥はsocietyを作らないことが導かれる

to mock a mockingbirdを読む(41)16章

The Forest Without a Name

ラッセルの森を抜けてCraigはMcSnurdのいとこのMcSnurtleにインタビューを行った。
McSnurtle曰く、我々は特別な鳥eを持つ。
eについて、以下の4つの法則が成り立つ

1
2
3
4
law 1.任意の鳥xとyについてexyが与えられた日に歌えば、yも歌う
law 2.任意の鳥xとyについてxとexyは決して同じ日には歌わない
law 3.任意の鳥xとyについてexyはxが歌わずyが歌う日に毎日歌う
law 4.任意の鳥xについて、ある鳥yが存在してyはeyxが歌うのと同じ日に歌う

Craigはこれらについて思考し、次の結論をえた
「この森の鳥はいまだかつて歌ったことが無い」
どのようにしてCraigはこの結論に至ったか

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
これは、Curryの森のProblem 1と本質的に同じ。
Curryの森の法則(再掲)
law 1. 与えられた日にyが歌えば、Pxyもその日に歌う
law 2. もしxが与えられた日に歌わなければPxyはその日に歌う
law 3. 与えられた日にxとPxyがどちらも歌うならば、yもその日に歌う
law 4. 各鳥xについてPyxが歌う日のみに歌うyが存在する

鳥がsilentであるとは、与えられた日にその鳥が歌わないことを言うことにする。
すると与えられた条件は次のように言い換えられる

law 1.もしyが与えられた日にsilentなら、exyもその日はsilent
law 2.もしxがsilentでなければ、exyはその日silent
law 3.xとexyがどちらもsilentであれば、yもその日silent
law 4.任意の鳥xについてeyxがsilentである日のみにsilentであるyが存在する

前回と同じ議論(歌うがsilentに変わっている)により
全ての鳥は毎日silentであることが導かれる

to mock a mockingbirdを読む(40)15章

Russell’s Forest

Craigはラッセルの森に到着した。
そこで、鳥類学者McSnurdにインタビューを行った。
この森では次の法則が成り立つと伺った。

1
2
law 1.任意の鳥xについて、xxが歌う日のみにaxが歌うような特別な鳥aがいる
law 2.任意の鳥xについて、ある鳥x'が存在して、任意の鳥yについてxyが歌わない日のみにx'yは歌う

Problem 1

上の2つの法則は矛盾する。なぜか

1
2
3
4
5
6
7
McSnurdから聞いた法則が真実だとすると
任意の鳥xについて、xxが歌う日のみにaxが歌うような特別な鳥aがいる
law2より、ある鳥a'が存在して任意の鳥xについてaxが歌わない日のみに歌うa'xがいる。
law1よりxxが歌う日のみにaxが歌うので、axが歌わない日はxxも歌わない。
よってxxが歌わない日に歌うa'xが存在する
特にxにa'をとると
a'a'が歌わない日に歌うa'a'が存在することになり、これは矛盾である

Problem 2 A Follow-up

Craigは前の結果に落胆し、別の鳥類学者を探したところ
McSnurdの兄弟もまた鳥類学者であることが判明したのでインタビューを行った。
すると、次の法則が成り立つということを伺った

1
2
law 1.任意の鳥xについて、xが歌わない時のみに歌うNxが存在する
law 2.この森にはSage Birdがいる

しばらくのち、CraigはこのMcSnurdも兄弟と同じくらい悪いことに気づく。
それはなぜか

1
2
3
4
McSnurdから聞いた法則が真実だとすると
任意の鳥xについてNx≠xである
この森にはSage BirdがいるのでNは何らかの鳥が好き。
よってNx=xであり矛盾する

Problem 3 A Second Follow-up

Craigはさらに別のMcSnurdの兄弟も鳥類学者であることがわかったのでインタビューを行った。
すると、次の法則が成り立つことを伺った

1
2
law 1.この森にはSage birdがいる
law 2.ある鳥Aが存在して、任意の鳥xとyについてxとyがどちらも歌わない日にAxyは歌う

McSnurdはこれでもうトラブルには巻き込まれないと言っているが
この三番目のMcSnurdの話は筋が通っているか

1
2
3
4
McSnurdから聞いた法則が真実だとする。
Sage birdがいるので任意の鳥xについてAxは何らかの鳥が好き
よってAxy = y
xもyも歌わないときにyは歌うのでyについて矛盾が起こる。

to mock a mockingbirdを読む(39)14章

Curry’s Lively Bird Forest

Craigはカリーの森に到着した。
そこで最初にしたことは、鳥類学者Byrdにインタビューすることであった。
Byrdが言うには、「この森ではある鳥はある日に鳴く。
私の目的はどの鳥がどの日に鳴くかを決定することである。」
Byrdは次の4つの法則を見つけた。

1
2
3
4
law 1. 与えられた日にyが歌えば、Pxyもその日に歌う
law 2. もしxが与えられた日に歌わなければPxyはその日に歌う
law 3. 与えられた日にxとPxyがどちらも歌うならば、yもその日に歌う
law 4. 各鳥xについてPyxが歌う日のみに歌うyが存在する

ByrdはCraigに、統一した一つの法則が見出せないか相談し、
Craigは次のシンプルな統一法則を見つけた

1
law. 全ての鳥は全ての日に歌う

Problem 1

なぜ上の統一法則が従うか

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
まず、もしxが歌う日全てでyが歌うなら
Pxyは全ての日で歌わなければならない。
もしxが歌わなければPxyは歌う(law2)。
もしxが歌うなら、yもその日に歌う(仮定より)
よってPxyもその日に歌う(law1)
xがその日歌うか歌わないかに関わらず
Pxyは全ての日で歌う

今、任意の鳥xが与えられたとして、xは全ての日で歌うことを示す。
law4よりPyxが歌う日のみに歌うyが存在する。
yが歌う任意の日を考える。
Pyxもその日歌う(law4)。
またyが歌うのでxもその日歌う(law3)
これにより、yが歌う全ての日でxが歌うことが示された。
また、前の段で検討したのと同様にPyxも毎日歌う。
yはPyxと同じ日に歌うので結局yも毎日歌う。
従って、何の日に限らずyとPyxは歌うのでxも毎日歌う(law3)

Problem 2

4番目の法則の代わりに森にLarkがいる場合全ての鳥は毎日歌うか
またLarkの代わりにCardinalがいる場合はどうか
またLarkとCardinalが両方いる場合はどうか

1
2
3
4
5
6
7
LとCがそれぞれ単体で与えられた場合は全ての鳥が毎日歌うことを示す方法はないが
LとCが両方与えられた場合は次のようにlaw 4を導くことができる。
Lが存在すると、任意の鳥xはLx(Lx)が好きであることは以前示した。
任意の鳥xについてCPxはある鳥yが好きである。
CPxy=y
Pyx=y
が成り立つのでPyxとyは同じ鳥である故にlaw 4が成立する

Problem 3

再びlaw 4がなくlaw 1からlaw3までが成り立っているとする。
ここで、全ての鳥が毎日歌うことを示すsingle combinatorial birdを見つけよ

1
2
3
4
5
6
Axyz=x(zz)yとなるようなAを考える。
任意の鳥xとyについて
APxy=P(yy)x
よって
APx(APx)=P(APx(APx))x
y=APx(APx)と置くとy=Pyxとなる

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

Problem 22 Similarity

鳥A1と鳥A2がsimilarであるとは任意の鳥xについて
A1とA2が同じレスポンスをかえすことを意味する。
つまり

1
A1x = A2x

が成り立つ

Problem 18で任意の賢人鳥ΘについてOΘも賢人鳥であることを見た。
ΘとOΘは必ずしも同じ鳥あることを示してはいない。
しかし、ΘとOΘはsimilarであることは示せる。どうやるか

1
2
3
Θは賢人鳥なのでΘx = x(Θx)
またOΘx=x(Θx)
よってΘx=OΘxが成り立つのでΘとOΘはsimilarである

Problem 23

ある森がextensional(外延的)であるとは、2つの異なる鳥は似ていないことを意味する。
言い換えると、もし鳥A1が鳥A2とsimilarであった場合、A1=A2が成り立つ。

extensionalな森では、Owlは全ての賢人鳥を好きであることを証明せよ

1
2
3
extensionalな森では、Θが賢人鳥だとするとOΘはΘとsimilarである。
よってOΘ=Θとなり、Owlは賢人鳥が好きである
森はextensionalであるので、Owlは全ての賢人鳥が好きである

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

Problem 18

Owlの面白い特徴の一つは賢人鳥Θについて
OΘもまた賢人鳥になることである。
これを証明せよ

1
2
3
4
任意のxをとるとxはΘxが好きである。
Problem 17の結果よりxはx(Θx)が好きである。
x(Θx)はOΘxであるのでxはOΘxが好きである。
よってOΘは賢人鳥である。

Problem 19

Owlの別の面白い特徴の一つは賢人鳥Θについて
ΘOもまた賢人鳥になることである。
これを証明せよ

1
2
3
4
5
6
7
8
9
10
Θが賢人鳥だとすると
任意のyについて
Θy=y(Θy)
特に
ΘO=O(ΘO)
任意のxについて
ΘOx=O(ΘO)x
=x(ΘO)x
これはxがΘOxを好きだということなので
ΘOは賢人鳥である。

Problem 20

Owlは賢人鳥のみを好きである。
もし任意の鳥Aについて
OA=Aが成り立っているとするとAは賢人鳥である。
これを示せ

1
2
3
4
5
OA=Aが成り立っているとすると
A=OA
任意のxについて
Ax=OAx=x(Ax)
xはAxが好きなのでAは賢人鳥である。

Problem 21

この問題はproblem 19の結果を一般化するものである。
ある鳥Aがchoozyであるとは、Aが賢人鳥だけを好きであることを意味する。
Owlはchoozyである。しかし、choozyな鳥はOwlだけではない
賢人鳥をΘとし、choozyな任意の鳥AについてΘAもまた賢人鳥であることを示せ。

1
2
Θは賢人鳥なのでAはΘAが好きである
Aはchoozyなので、ΘAもまた賢人鳥である

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が好き

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

Problem 10 Currys Sage Bird

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

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

THE TURING BIRD

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

1
Uxy = y(xxy)

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

Problem 11 Finding a Turing Bird

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

1
2
3
4
5
6
7
8
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を構成できることにある。
どうやるか

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

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

Problem 8 Queer Birds and Mockingbirds

QとMを用いて賢人鳥を導け

Discussion
regular combinatorとは、proper combinatorの一種で、
その定義の左側においてもっとも左にある変数(xとする)が
右側においてももっとも左にあり、1度だけxが出現するものを言う。

具体的にはCxyz=xzyはregularである。右辺の一番左側にxが一度だけ出現しているからである。
逆にRxyz=yzxはregularではない
同様にMx=xxはregularではない。xが2回出現しているからである。
regularなコンビネータとしてはB,C,W,L,S,I,Kがあり
T,R,F,V,Qはregularではない

Problem 1,2,3,4では3つのproper combinatorから賢人鳥を導いた。
うちMだけregularでないコンビネータになる。
Problem 7では3つのregularなコンビネータから賢人鳥を導いた。
Problem 8(本問)では2つのregularでないコンビネータMとQから賢人鳥を導く。
次に2つのregularなコンビネータから賢人鳥が導けることを見ていく

1
2
3
4
5
6
7
8
Lx(Lx)
=M(Lx)
=QLMx
またL=QMなので
Lx(Lx)
=QLMx
=Q(QM)Mx
よってQ(QM)Mは賢人鳥である

Problem 9

StarlingとLarkから賢人鳥が導けることを示せ

1
2
Lx(Lx)=SLLxなので
SLLが賢人鳥である