不動点パズル14：対称記号列（問19の解答後半）

（前回はこちら）

機械に、ある記号列 x を入力すると、ある記号列 y をもたらす。この機械には4つの規則がある。

規則Q　Qx → x
（任意の記号列 x に対して、記号列 Qx は x をもたらす）
規則C　x → y ならば、Cx → yQy
（x が y をもたらすならば、Cx は y の随伴 yQy をもたらす）
規則R　x → y ならば、Rx → yy
（x が y をもたらすならば、Rx は yy、すなわち y の反復をもたらす）
規則V　x → y ならば、Vx → y←
（x が y をもたらすならば、Vx は y の反転をもたらす）

対称記号列（回文記号列）：反転しても同じである記号列。記号列がその反転と等しいとき、その記号列は対称であるという。

前回、問19で、それ自身をもたらす対称記号列 VVCVVQVVCVV を見つけた。今回は、問19の後半部分、何種類あるかについて考えよう。前回の解答の途中でさらりと触れたが、実は、この問題の本での解答をすでに見ている。しかし、その解答を見てもまだわかっていないので、解答の解説を書くつもりで記載する。


問題19　CQC 以外で、それ自身をもたらす対称記号列を見つけよ。それは何種類あるだろうか。

この問題の解答欄には以下のようにあった。

VVCVVQVVCVV は、それ自身をもたらす対称記号列になる。z を偶数個の V からなる記号列とするとき、zCzQzCz もそれ自身をもたらす対称記号列になる。

z = VV（2個の V からなる記号列）としたとき、zCzQzCz は VVCVVQVVCVV である。

z を偶数個の V からなる記号列とするとき、zCzQzCz もそれ自身をもたらす対称記号列になるのだから、VVVVCVVVVQVVVVCVVVV（z = VVVVとしたとき）も、それ自身をもたらす対称記号列になる。

では、z が奇数個の場合は、それ自身をもたらす対称記号列にならないのだろうか。たとえば、VCVQVCV がどのような記号列をもたらすのかを考えてみる。

VCVQVCV がもたらす記号列を x とすると、

VCVQVCV → x　・・・・・①

と書ける。VCVQVCV は V からはじまる記号列であるため、何らかの記号列をもたらすならば規則V に従う。そのため、

CVQVCV → x←　・・・・・②

ならば、VCVQVCV は x をもたらす。

CVQVCV は C からはじまる記号列であるため、何らかの記号列をもたらすならば規則C に従う。そのため、x← を、y←Qy← とおくと、

VQVCV → y←　・・・・・③

ならば、CVQVCV は x← をもたらす。

VQVCV は V からはじまる記号列であるため、何らかの記号列をもたらすならば規則V に従う。そのため、

QVCV → y

ならば、VQVCV は y← をもたらす。

規則Q より、QVCV は VCV をもたらす。
QVCV は VCV をもたらすので、VQVCV は VCV（VCV の反転）をもたらす。
VQVCV は VCV をもたらすので、CVQVCV は VCVQVCV をもたらす。
CVQVCV は VCVQVCV をもたらすので、VCVQVCV は VCVQVCV をもたらす。

VCVQVCV が、それ自身をもたらす対称記号列となった。VCVQVCV は、zCzQzCz で、z = V（Vが1個）の記号列である。つまり、z が奇数個の V からなる記号列のひとつである。どこかで何か間違ったのだろうか。

3つ以上の奇数の場合はどうだろうか。

先ほど見た記号列 VCVQVCV では、QVCV が VCV をもたらすことが、最終的に VCVQVCV は VCVQVCV をもたらす条件となっている。

前回求めた対称記号列 VVCVVQVVCVV についてみると、
（規則Q）QVVCVV → VVCVV
（規則V）QVVCVV → VVCVV であるので、VQVVCVV → VVCVV
（規則V）VQVVCVV → VVCVV であるので、VVQVVCVV → VVCVV
（規則C）VVQVVCVV → VVCVV であるので、CVVQVVCVV → VVCVVQVVCVV
（規則V）CVVQVVCVV → VVCVVQVVCVV であるので、
VCVVQVVCVV → VVCVVQVVCVV
（規則V）VCVVQVVCVV → VVCVVQVVCVV であるので、
VVCVVQVVCVV → VVCVVQVVCVV
であり、QVVCVV → VVCVV であることが、最終的に VVCVVQVVCVV → VVCVVQVVCVV の条件となっている。

zCzQzCz についても、QzCz → zCz であるので、zCzQzCz → zCzQzCz といえるだろう。

QzCz → zCz
QzCz → zCz であるので、VQzCz → zCz
……（記号列zの V の個数分、繰り返し）……
zQzCz → zCz であるので、CzQzCz → zCzQzCz
CzQzCz → zCzQzCz であるので、VCzQzCz → zCzQzCz
……（記号列zの V の個数分、繰り返し）……
z_n-1CzQzCz → zCzQzCz であるので、zCzQzCz → zCzQzCz
のようになるはずである。（z_n-1 は、z の V の個数より1少ない個数の V からなる記号列）

このなかで、反転の対象となる記号列は、zCz と zCzQzCz で、z が V からなる記号列である場合は、V の個数にかかわらず、zCz と zCzQzCz を反転しても同じ記号列となる（つまり、対称記号列である）。

本の解答に、「偶数個の V」とあるからには何らかの理由があると思うのだが、現時点ではその理由がわかっていない。本に記載されている解答は間違いではない。「z を偶数個の V からなる記号列とするとき、zCzQzCz もそれ自身をもたらす対称記号列になる」ことは間違いではない。

（つづく）