2019/08/26

不動点パズル19:特殊記号列

(前回はこちら

さて、ここからが、しっかりと理解したいところだ。

『スマリヤンのゲーデル・パズル』のなかで、アーニーはまず、特殊記号列について説明している。
「記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列と呼ぶことにする。したがって、どの特殊記号列Θも、y1 と y2 が同じ記号列をもたらすならば、Θy1 とΘy2 は同じ記号列をもたらす。記号C、R、V だけから作られた任意の記号列は、どれも特殊記号列になる。任意の特殊記号列Θと任意の記号列 x に対して、ΘQx がもたらす(または x をもたらす任意の記号列 y に対してΘy がもたらす)記号列をΘ(x)で表す。たとえば、(RQx は xx をもたらすので)R(x) は x の反復になる。また、V(x) は x の反転、C(x) は x の随伴 xQx、RC(x) は x の随伴の反復、CV(x) は x の反転の随伴になる。ここまではいいかね」
うん。よくない。

しかし、まったくわからないというわけではない。何となくわかるような、わからないようなという感じである。こんなときは、ゆっくりじっくり確認していくことだ。

このなかでわかっていない感が一番強いところは、特殊記号列の性質のところである。なので、後回しにして、まずは具体例から見ていきたいと思う。
任意の特殊記号列Θと任意の記号列 x に対して、ΘQx がもたらす(または x をもたらす任意の記号列 y に対してΘy がもたらす)記号列をΘ(x)で表す。たとえば、(RQx は xx をもたらすので)R(x) は x の反復になる。また、V(x) は x の反転、C(x) は x の随伴 xQx、RC(x) は x の随伴の反復、CV(x) は x の反転の随伴になる。
ここで書かれていることを別の言葉でいえば、たとえば、xx(x の反復)を R(x) と表現しよう、ということである。

これまでの規則をあらためて書いておこう。
規則Q Qx → x
(任意の記号列 x に対して、記号列 Qx は x をもたらす)
規則C x → y ならば、Cx → yQy
(x が y をもたらすならば、Cx は y の随伴 yQy をもたらす)
規則R x → y ならば、Rx → yy
(x が y をもたらすならば、Rx は y の反復 yy をもたらす)
規則V x → y ならば、Vx → y
(x が y をもたらすならば、Vx は y の反転 y をもたらす)
規則P x → y ならば、Px → yy
(x が y をもたらすならば、Px は y の回文 yy をもたらす)
規則M x → y ならば、Mx → y
(x が y をもたらすならば、Mx は y をもたらす)
規則Q と 規則R から次のことがいえる。
Qx は x をもたらすので、RQx は xx をもたらす。
R(x) を使って表現すると、
Qx は x をもたらすので、RQx は R(x) をもたらす。
ということである。

規則Q は、任意の記号列 x に対して成り立つ。つまり、
任意の記号列 x に対して、RQx は R(x) をもたらす。
ということである。

ここで、R をΘと置き換えると、
任意の記号列 x に対して、ΘQx は Θ(x) をもたらす。
「任意の特殊記号列Θと任意の記号列 x に対して、ΘQx がもたらす記号列をΘ(x)で表す」というのは、こういうことだ。

では、特殊記号列の性質について、だ。
「記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列と呼ぶことにする。したがって、どの特殊記号列Θも、y1 と y2 が同じ記号列をもたらすならば、Θy1 とΘy2 は同じ記号列をもたらす。記号C、R、V だけから作られた任意の記号列は、どれも特殊記号列になる」
一文ずつ区切ってみよう。
「記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列と呼ぶことにする」
少し入り組んだ表現であるので、骨格を明確にして、これまでと同じように、「もたらす」を記号「→」で表現すると、
・ΘQx → y(記号列ΘQx がある記号列 y をもたらす)
・z → x ならば、Θz → y(z が x をもたらすならば、Θz は y をもたらす)
この2つが成り立つ記号列Θのことを特殊記号列と呼ぼうと言っている。

何か具体例がほしい。そこで、これまでの問題を見直していると、問10(「不動点パズル06」参照)がよさそうだ。問10では、記号列 x で、Rx が x の反復をもたらす記号列として、CQC と RQRQ を挙げていて、具体例としてあてはめることができそうだ。

特殊記号列Θを R として、先ほどの特殊記号列の性質にあてはめると、
・RQx → xx
・z → x ならば、Rz → xx
たとえば、x = CQC で見ると、
・RQCQC → CQCCQC
・z → CQC ならば、Rz → CQCCQC
CQC は、それ自身をもたらす記号列であるので、z = CQC とすることができる。
・RQCQC → CQCCQC
・CQC → CQC ならば、RCQC → CQCCQC
これを特殊記号列の性質の言葉どおりに書くと、『記号列 RQCQC が記号列 CQCCQC をもたらすならば、CQC をもたらす 記号列 CQC に対しても、RCQC は RQCQC と同じく CQCCQC をもたらす』ということになる。

具体例があることで、少しイメージがつかめたような気がする。

次は、特殊記号列の性質からあきらかである。
「したがって、どの特殊記号列Θも、y1 と y2 が同じ記号列をもたらすならば、Θy1 とΘy2 は同じ記号列をもたらす」

さて、その次はどうだろうか。
「記号C、R、V だけから作られた任意の記号列は、どれも特殊記号列になる」
たとえば、記号P や M から作られた記号列は特殊記号列にはなりえないのだろうか。この点に関しては、まだ考えていない。

つづく

0 件のコメント:

コメントを投稿

ブログ アーカイブ