不動点パズル18：移動（問24の解答）

（前回はこちら）

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

規則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 そのものとする。

今回は、問24について。

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

（解答）
まずは、xJKL をもたらすような x を探す。

x → xJKL　・・・・・①

規則Q、C、R、V だけを使った記号列 x で xy をもたらすものがあるかどうかは未解決問題であったため、規則M を使えるように、x を M からはじまる記号列として考えていこう。x = Mx₁ とすると、①は、

Mx₁ → Mx₁JKL　・・・・・①'

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

x₁ → LMx₁JK　・・・・・②

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

ここで、x₁ = Mx₂ とすると、②は、

Mx₂ → LMMx₂JK　・・・・・②'

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

x₂ → KLMMx₂J　・・・・・③

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

同様に、x₂ = Mx₃ とすると、③は、

Mx₃ → KLMMMx₃J　・・・・・③'

規則M の条件より、

x₃ → JKLMMMx₃　・・・・・④

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

CQyC → yCQyC の y を JKLMMM としたとき、④を満たす。このとき、x₃ = CQJKLMMMC である。したがって、xJKL をもたらすような記号列 x は、

x = Mx₁ = MMx₂ = MMMx₃ = MMMCQJKLMMMC
∴xJKL をもたらすような記号列 x は、MMMCQJKLMMMC

これを一般的にして、xy をもたらすような記号列 x を考えてみよう。

さきほどの x → xJKL のときに使った規則をならべて書いてみると、

CQJKLMMMC → JKLMMMCQJKLMMMC
MCQJKLMMMC → KLMMMCQJKLMMMCJ
MMCQJKLMMMC → LMMMCQJKLMMMCJK
MMMCQJKLMMMC → MMMCQJKLMMMCJKL

となる。JKL の移動の様子がわかるように太字にした。

規則M は先頭の記号を末尾に1文字ずつ移す。そのため、一般的に xy をもたらすような記号列を考えると、y の文字数（記号列の長さ）分の M が必要であることがわかる。

したがって、xy をもたらすような記号列 x には、任意の記号列 y と、y と同じ長さをもつ M からなる記号列 z を使った、zCQyzC がある。
（また、RQyRQ → yRQyRQ を使った zRQyzRQ も同様の記号列となりうる。）

（つづく）