2019/08/09

不動点パズル02:随伴(問1~問3の解答)

(前回はこちら

アーニーの機械は記号列を操作する機械で、ある記号列xを入力すると、ある記号列yをもたらす。いま、機械には2つの規則がある。2つの規則、規則Qと規則Cをあらためて見ておこう。
規則Q 任意の記号列xに対して、記号列Qxはxをもたらす。
規則C xがyをもたらすならば、Cxはyの随伴yQyをもたらす。

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

問1 それ自身をもたらすような記号列を見つけよ。
問2 それ自身の随伴をもたらすような記号列を見つけよ。
問3 それ自身の随伴の随伴をもたらすような記号列を見つけよ。
問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をもたらす)
わかりやすくなるかどうか若干不安があるが、以降これでいこう。

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

*****

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

(解答)
規則Qより、Qx→xであるので、CQx→xQxが成り立つ。
xがCのとき(以下「x = C のとき」と表現する)、CQC→CQCとなる。
∴それ自身をもたらすような記号列はCQC

*****

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

(解答)
求める記号列をxとして、
x→xQx ・・・・・①
となるような記号列を探す。
随伴をもたらす記号列だから、xはCからはじまる記号列。そこで、x = Cx1とすると、①は、
Cx1→Cx1QCx1 ・・・・・①’
と書ける。このとき、規則Cの条件より、
x1→Cx1 ・・・・・②
が成り立たなければならない。②の式は規則Qにあてはまらないので、規則Cにあてはめるため、x1 = Cx2とすると、
Cx2→CCx2 ・・・・・②’
と書ける。規則Cの条件を満たすようにするには、x2 = QCC とすればいい(②’の式での出力先の記号列にはQがないので、x2 = Qx3とすると、x3 = CC)。求める記号列はxであるため、
x = Cx1 = CCx2 = CCQCC
∴それ自身の随伴をもたらすような記号列はCCQCC

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

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

(解答)
求める記号列をxとして、
x→xQxQxQx ・・・・・①
となるような記号列を探す。
随伴をもたらす記号列だから、xはCからはじまる記号列。そこで、x = Cx1とすると、①は、
Cx1→Cx1QCx1QCx1QCx1 ・・・・・①’
と書ける。このとき、規則Cの条件より、
x1→Cx1QCx1 ・・・・・②
が成り立たなければならない。②の式は随伴をもたらすことを意味するので、x1はCからはじまる記号列。x1 = Cx2とすると、
Cx2→CCx2QCCx2 ・・・・・②’
と書ける。このとき、規則Cの条件より、
x2→CCx2 ・・・・・③
が成り立たなければならない。③の式は規則Qにあてはまらないので、規則Cにあてはめるため、x2 = Cx3とすると、
Cx3→CCCx3 ・・・・・③’
規則Cの条件を満たすようにするには、x2 = QCCC とすればいい(③’の式での出力先の記号列にはQがないので、x3 = Qx4とすると、x4 = CCC)。求める記号列はxであるため、
x = Cx1 = CCx2 = CCCx3 = CCCQCCC
∴それ自身の随伴の随伴をもたらすような記号列はCCCQCCC

問4は次回にまわそう。

0 件のコメント:

コメントを投稿

ブログ アーカイブ