Compatible birds

同じでも異なっていてもよい2つの鳥A,Bが互換性がある(compatible)とは
次の条件を満たすときをいう

1

A x = y　かつ B y = x

Problem 6

Problem1のC1とC2の元で
任意の2つの鳥A,Bは互換性があることを示せ

解

1
2
3

ABは不動点yを持つ
x = B yとおくと
A x = A B y = y

Happy birds

鳥Aが幸せ(happoy)であるとは、それ自身と互換性があることを言う
つまり

1

A x = y かつ A y = x

Problem 7

少なくとも1つの鳥を好きな任意の鳥はhappyであることを示せ

つまりコンビネータが不動点を持つ時happyであるということを証明せよという問いである

解

1
2
3
4

AがBを好きであるとき
AB = Bであるので
x=B y=Bとおけば
Ax = y かつ Ay = x

normal birds

ある鳥が正規(normal)であるとは、少なくとも1つの鳥を好きなことを言う
Problem 7で示したとおり各normalな鳥はhappyである
この逆は必ずしも成り立たず、happyな鳥がnormalであるとは限らない

Problem 8

Problem1のC1の元で
森に少なくとも1つのhappyな鳥がいるとき
少なくとも1つのnormalな鳥がいることを証明せよ

解

1
2
3
4
5
6
7
8

Hがhappy birdだと仮定すると
Hx = y Hy = xなるxとyが存在する
xをHyで置き換えると
H(Hy) = y
条件C1の元でHとHを合成した鳥Bが存在する。
By = H(Hy) = y
つまりBy = y
Bはyが好き、よってBはnormalである

Problem 4

Problem1のC1の元で
C=ABとなるとき、CがagreeableであればAもagreeableであることを示せ。

解

1
2
3
4
5
6
7
8

C x = A B x
またCがagreeableなので
C x = D B x
となるようなD Bについて少なくとも一つのxが存在する。よって
A B x = D B x
B xをyとおけば
A y = D y
よってAもagreeable

Problem 5

Problem1のC1の元で
任意の鳥A,B,Cについて、各xについて
次の条件を満たすDが存在することを示せ

1

D x = (A (B (C x)))

解

1
2
3
4
5
6

C1より任意のA,Eについて
D x = A (E x)
C1より任意のB,Cについて
E x = B (C x)
これらより
D x = A (B (C x))となるDが存在する

本書には、この事実は非常に有用だとあります

二つの鳥A,Bがある鳥xに同意(agree)するとは、
xへの反応が等しいことを言う

1

A x = B x

Aがagreeableであるとは各Bに対して少なくとも一つのxが存在し
AとBが同意することである。
言い換えるとAがagreeableであるとは各Bについてある鳥xが存在し

1

A x = B x

を満たす。

Problem 3

以前の条件C1の元で
条件C2の代わりにagreeableな鳥Aが存在するとき
各鳥が少なくとも一つの鳥を好きであることを保証するには充分か

解

AがBAに同意する状況を考える

1
2
3

Ax = BAx
BAx = B(BAx)
よってAxはBの不動点

つまり、この条件でも充分だということになる

ボーナス問題

Problem 3はProblem 1の特別なケースでしかない。
mockingbirdはagreeableである必要があるか

解

1

任意のBについてM x = B xにおいて、xをBとおけばMはagreeable

ある鳥xが自己中心的(egocentric)であるとは、
自分自身を好きなことをいう。
式で表すと次のようになる。

1

xx = x

Problem 2

前回やった条件C1、C2の元では少なくとも1つの鳥が自己中心的である。
これを示せ

解

1
2
3
4
5

Mは少なくとも一つの鳥Eが好きなので
ME = E
またMはmockingbirdなので
ME = E E
よってE = E EとなりEはEが好きなためegocentricである。

鳥Aが鳥Bを好きであるとは、次の条件が満たされるときを言う

1

AB = B

注：これは、数学的にはBがAの不動点(fixed point)であることを表している

以下の2条件を考える

C1(the composition condition)

任意の鳥A,B(同じでも異なっていても良い)について鳥Cが存在し
任意の鳥xについて

1

Cx = A(Bx)

C2(the mockingbird condition)

鳥が住んでいる森にはmockingbird Mが存在する

Problem 1 どちらの噂が正しい？

上のC1,C2の元で次の2つのうちどちらが正しいか
1.この森の各鳥は、少なくとも1つ好きな鳥がいる
2.この森には、どの鳥からも好かれていない鳥が少なくとも1羽いる

これは、上の注を元に考えると
1.はすべてのコンビネータが不動点を持つかどうかという問いになる

これは次のようなX’を考えることで1が正しいことが分かります

1
2
3
4

X'=M(XM)
XX'=XM(XM) = M(XM) = X'

XX'=X'

スマリヤンの本の9章から、コンビネータ論理についての話が始まります。
ただし、コンビネータという言葉を使わずにコンビネータのことを鳥(bird)と呼ぶことにして
話が展開されてゆきます。本書を読み進めていくと最終的には不完全性定理に行きつきます。
楽しみにしておいてください。

鳥Aと鳥Bがいるとして、鳥ABとはBの名前を聞いたときに鳥Aによって名前がつけられた鳥のことを表します。
これだと長いので鳥Aへの鳥Bの反応をABと書くということにします。

一般的にABはBAと同じとは限りません(交換法則が成り立たない)

さらに鳥Cも加えたとき、
一般的にA(BC)は(AB)Cと同じとは限りません(結合法則が成り立たない)

単にABCと書いたとき、これがA(BC)を意味するのか(AB)Cを意味するのか知ることはできません。
注：本書にはこう書かれていますが一般的にはABCは(AB)Cを表すこととし(関数適用が左結合だとみなす)
そうすることによって生じる曖昧さもありません。
本サイトではこちらを採用することとします。
追記：本書でも11章で左結合の記法が採用されます。

Mockingbirds

常に次の条件をみたす鳥Mをmockingbird(ものまね鳥)と呼ぶ

1

Mx = xx

Mがmockingbirdと呼ばれるのは、Mのxへの反応は
xのx自身への反応と同じという単純な理由によります。

Composition

任意の鳥A,B,C,x(異なっている必要はない)について
次の条件を満たすときCはAとBの合成(composition)と呼ぶ

1

Cx = A(Bx)

Cのxへの反応は、Aの(Bのxへの反応)への反応と同じことを表します。

このサイトについて

このサイトは、コンビネータと呼ばれる高階関数について
色々と調べてみようと思い立ち上げたものです。
学術的にはコンビネータ論理(結合子論理)と呼ばれるものがあり、
これは本来論理学での量化変数(∀など)を除去するために考案されたものですが
計算機科学のモデルとしても使われるようになったという経緯があります。
コンビネータはラムダ計算とも関連があり、ラムダ式をコンビネータに変換することも簡単にできます。
変換の仕方も何種類もあり、いずれこのサイトでも取り上げる予定です。
まずは、レイモンド・スマリヤンの著書「to mock a mockingbird」のPart Three(9章)以降を参考に
コンビネータがどういうものかみていくことから始めたいと思います。
解答は基本的に本の解答にそってつけています
詳しい解説のないエクササイズの解答などは私なりに解いた結果を載せています。