不動点パズル13：対称記号列（問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について、『スマリヤンのゲーデル・パズル』には、解答は載っているが、どのように導いたのかは載っていない。したがって、以下記載しているのは、僕の試行錯誤の過程である。


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

（解答）
対称記号列とは、前から読んでも後ろから読んでも同じ記号列であるので、求める記号列を x とすると、

x = x←

である。

求める記号列は、それ自身をもたらす記号列であるので、

x → x　・・・・・①

となる対称記号列 x を探す。対称記号列であるので、反転しても同じものである。したがって①は、

x → x←　・・・・・②

とも書き換えられる。

そこで、x は V からはじまる対称記号列（そして V で終わる記号列）として、x = Vx₁V とすると、x₁ は対称記号列であり、①②は、それぞれ

Vx₁V → Vx₁V　・・・・・①’
Vx₁V → [Vx₁V]←　・・・・・②'

と書ける。

①'について、規則V の条件より、

x₁V → [Vx₁V]←　・・・・・③

②'について、規則V の条件より、

x₁V → Vx₁V　・・・・・④

とならなければならない。

（CQyC → yCQyC や RQyRQ → yRQyRQ を使いたくなるが、対称記号列とならない可能性が高いので、別の方法をとる。）

③について、反転のかたちをしており、x₁ は対称記号列であるので、x₁ = Vx₂V とすると、x₂ は対称記号列であり、また③、④はそれぞれ、

Vx₂VV → [VVx₂VV]←　・・・・・③'

Vx₂VV → VVx₂VV　・・・・・④'

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

x₂VV → VVx₂VV　・・・・・⑤
x₂VV → [VVx₂VV]←　・・・・・⑥

とならなければならない。

⑤について、随伴のかたちに似ており、x₂ は対称記号列であるので、x₂ = Cx₃Qx₄C（x₄ は x₃ の反転とする）とすると、

Cx₃Qx₄CVV → VVCx₃Qx₄CVV　・・・・・⑤'
Cx₃Qx₄CVV → [VVCx₃Qx₄CVV]←　・・・・・⑥'

と書ける。

⑤'でもたらされる記号列 VVCx₃Qx₄CVV について、これを随伴のかたちにするため、VVCx₃ = x₄CVV となるような x₃、x₄ を考えると、x₃、x₄ ともに VV であればよい。x₄ は x₃ の反転であることも満たしている。x₃ = x₄ = VV を、⑤'、⑥'に当てはめてみると、

CVVQVVCVV → VVCVVQVVCVV　・・・・・⑤'
CVVQVVCVV → [VVCVVQVVCVV]←　・・・・・⑥'

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

VVQVVCVV → VVCVV　・・・・・⑦

とならなければならない。

⑦は規則V の条件より、 VQVVCVV → VVCVV とならなければならず、VQVVCVV → VVCVV は、QVVCVV → VVCVV とならなければならない。QVVCVV → VVCVV は規則Q を満たしている。

それ自身をもたらす対称記号列 x は、次のようになる。

x = Vx₁V = VVx₂VV = VVCx₃Qx₄CVV = VVCVVQVVCVV
∴それ自身をもたらす対称記号列として、VVCVVQVVCVV が存在する。

（ここで示した解き方は、解答の記号列を見て考えたものであり、解答に合わせるように解いている。ひょっとすると、もう少しうまい解き方があるかもしれない。）

それ自身をもたらす対称記号列が何種類あるかについては次回に回そう。

（つづく）