不動点パズル17：移動

（前回はこちら）

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

規則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● をもたらす）

x● は、記号列 x の先頭の記号を末尾に移した記号列を意味する。記号列が1文字だけの記号の場合には、x● は x そのものとする。たとえば、x が KGS ならば、x● は GSK となる（x の先頭の記号 K を末尾に移動）。

問題は以下。

問23　x が x● をもたらすような x を見つけよ。

問24　任意の記号列 y に対して、規則Q、C、R、V だけを使った記号列 x で xy をもたらすものがあるかどうかは未解決問題だとすでに述べた（「不動点パズル11：未解決問題」参照）。しかし、規則M を追加すると、任意の記号列 y に対して、記号列 x が xy をもたらすような x を比較的簡単に見つけることができる。それは、どのようにすればよいだろうか。たとえば、x が xJKL をもたらすような x を見つけよ。

問23についてはここで解答しよう。

問23　x が x● をもたらすような x を見つけよ。

（解答）

x → x●　・・・・・①

となる x を探す。

x を M からはじまる記号列として、x = Mx₁ とすると、①は、

Mx₁ → Mx₁●　・・・・・①'

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

x₁ → Mx₁　・・・・・②

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

CQyC → yCQyC の y を M とすると、CQMC → MCQMC となり、②を満たす。
求める記号列 x は、

x = Mx₁ = MCQMC
∴求める記号列は、MCQMC

RQyRQ → yRQyRQ を利用した、MRQMRQ も同様に求められる。

（つづく）