to mock a mockingbirdを読む(27)12章

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’は以下の条件を満たす。

W' x y = y x x

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

解

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文字の式として導出できる。
どうやればよいか

解

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

Problem 7

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

解

前章の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)
である。