2019/08/25

不動点パズル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 = Mx1 とすると、①は、
Mx1 → Mx1JKL ・・・・・①'
と書ける。このとき規則M の条件より、
x1 → LMx1JK ・・・・・②
とならなければならない。

ここで、x1 = Mx2 とすると、②は、
Mx2 → LMMx2JK ・・・・・②'
と書ける。このとき規則M の条件より、
x2 → KLMMx2J ・・・・・③
とならなければならない。

同様に、x2 = Mx3 とすると、③は、
Mx3 → KLMMMx3J ・・・・・③'
規則M の条件より、
x3 → JKLMMMx3 ・・・・・④
とならなければならない。

CQyC → yCQyC の y を JKLMMM としたとき、④を満たす。このとき、x3 = CQJKLMMMC である。したがって、xJKL をもたらすような記号列 x は、
x = Mx1 = MMx2 = MMMx3 = 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 も同様の記号列となりうる。)

つづく

0 件のコメント:

コメントを投稿

ブログ アーカイブ