不動点パズル02：随伴（問１～問３の解答）

（前回はこちら）

アーニーの機械は記号列を操作する機械で、ある記号列xを入力すると、ある記号列yをもたらす。いま、機械には2つの規則がある。2つの規則、規則Qと規則Cをあらためて見ておこう。

規則Q　任意の記号列xに対して、記号列Qxはxをもたらす。
規則C　xがyをもたらすならば、Cxはyの随伴yQyをもたらす。

問題は以下の4問であった。

問１　それ自身をもたらすような記号列を見つけよ。
問２　それ自身の随伴をもたらすような記号列を見つけよ。
問３　それ自身の随伴の随伴をもたらすような記号列を見つけよ。
問４　任意の記号列yに対して、ある記号列xで、yxをもたらすようなものが存在することを証明せよ。たとえば、どのようなxがAxをもたらすだろうか。


ここで、言葉で書いていくと文章が長くなりがちになるので、できるだけ記号を用いて表現したい。たとえば、「xがyをもたらす」というのを「x→y」と書くことにしよう。「もたらす」というのを「→」で表す。「x→y」のように記号で書いた表現を「式」と呼ぶ。そうすると、規則Qと規則Cの式はそれぞれ以下のように書ける。

規則Q　Qx→x
（任意の記号列xに対して、記号列Qxはxをもたらす）

規則C　x→yならば、Cx→yQy
（xがyをもたらすならば、Cxはyの随伴yQyをもたらす）

わかりやすくなるかどうか若干不安があるが、以降これでいこう。

この書き方は『スマリヤンのゲーデル・パズル』には載っておらず、このブログでの表記だ。また、解答方法もなるべく本の解答方法とは違う書き方（僕が考えた方法）をしていこうと思う。

＊＊＊＊＊

問１　それ自身をもたらすような記号列を見つけよ。

（解答）
規則Qより、Qx→xであるので、CQx→xQxが成り立つ。
xがCのとき（以下「x = C のとき」と表現する）、CQC→CQCとなる。

∴それ自身をもたらすような記号列はCQC

＊＊＊＊＊

問２　それ自身の随伴をもたらすような記号列を見つけよ。

（解答）
求める記号列をxとして、

x→xQx　・・・・・①

となるような記号列を探す。
随伴をもたらす記号列だから、xはCからはじまる記号列。そこで、x = Cx₁とすると、①は、

Cx₁→Cx₁QCx₁　・・・・・①’

と書ける。このとき、規則Cの条件より、

x₁→Cx₁　・・・・・②

が成り立たなければならない。②の式は規則Qにあてはまらないので、規則Cにあてはめるため、x₁ = Cx₂とすると、

Cx₂→CCx₂　・・・・・②’

と書ける。規則Cの条件を満たすようにするには、x₂ = QCC とすればいい（②’の式での出力先の記号列にはQがないので、x₂ = Qx₃とすると、x₃ = CC）。求める記号列はxであるため、

x = Cx₁ = CCx₂ = CCQCC
∴それ自身の随伴をもたらすような記号列はCCQCC

（考察）
・記号列CCQCCは、CCQCCの随伴CCQCCQCCQCCをもたらす。
・問１の解答途中で、CQx→xQxが成り立つことを確認した。CQx→xQxであるので、規則Cより、CCQx→xQxQxQxとなる。ここでx = CC としたのが問２の答えである。
・以下の規則は、本には載っていない（問題を解くためには使われている）

規則CQ　CQx→xQx（xの随伴）
（任意の記号列xに対して、記号列CQxはxの随伴xQxをもたらす）
規則CCQ　CCQx→xQxQxQx（xの随伴の随伴）
（任意の記号列xに対して、記号列CCQxはxの随伴の随伴をもたらす）

＊＊＊＊＊

問３　それ自身の随伴の随伴をもたらすような記号列を見つけよ。

（解答）
求める記号列をxとして、

x→xQxQxQx　・・・・・①

となるような記号列を探す。
随伴をもたらす記号列だから、xはCからはじまる記号列。そこで、x = Cx₁とすると、①は、

Cx₁→Cx₁QCx₁QCx₁QCx₁　・・・・・①’

と書ける。このとき、規則Cの条件より、

x₁→Cx₁QCx₁　・・・・・②

が成り立たなければならない。②の式は随伴をもたらすことを意味するので、x₁はCからはじまる記号列。x₁ = Cx₂とすると、

Cx₂→CCx₂QCCx₂　・・・・・②’

と書ける。このとき、規則Cの条件より、

x₂→CCx₂　・・・・・③

が成り立たなければならない。③の式は規則Qにあてはまらないので、規則Cにあてはめるため、x₂ = Cx₃とすると、

Cx₃→CCCx₃　・・・・・③’

規則Cの条件を満たすようにするには、x₂ = QCCC とすればいい（③’の式での出力先の記号列にはQがないので、x₃ = Qx₄とすると、x₄ = CCC）。求める記号列はxであるため、

x = Cx₁ = CCx₂ = CCCx₃ = CCCQCCC
∴それ自身の随伴の随伴をもたらすような記号列はCCCQCCC

問４は次回にまわそう。