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

（前回はこちら）

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

『スマリヤンのゲーデル・パズル』のなかで、アーニーはまず、特殊記号列について説明している。

「記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列と呼ぶことにする。したがって、どの特殊記号列Θも、y₁ と y₂ が同じ記号列をもたらすならば、Θy₁ とΘy₂ は同じ記号列をもたらす。記号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 をもたらす』という性質をもつとき、特殊記号列と呼ぶことにする。したがって、どの特殊記号列Θも、y₁ と y₂ が同じ記号列をもたらすならば、Θy₁ とΘy₂ は同じ記号列をもたらす。記号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 をもたらす』ということになる。

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

次は、特殊記号列の性質からあきらかである。

「したがって、どの特殊記号列Θも、y₁ と y₂ が同じ記号列をもたらすならば、Θy₁ とΘy₂ は同じ記号列をもたらす」

さて、その次はどうだろうか。

「記号C、R、V だけから作られた任意の記号列は、どれも特殊記号列になる」

たとえば、記号P や M から作られた記号列は特殊記号列にはなりえないのだろうか。この点に関しては、まだ考えていない。

（つづく）