不動点パズル07：反転

（前回はこちら）

機械に、ある記号列 x を入力すると、ある記号列 y をもたらす。この機械には3つの規則（規則Q、規則C、規則R）がある。

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

反転とは、その記号列の記号を逆の順に並べた記号列のことである。たとえば、LXQM の反転は MQXL である。任意の記号列 x の反転を x← と表す。

問題は以下である。

問12　それ自身の反転をもたらすような記号列を見つけよ。

問13　それ自身の反復の反転をもたらすような記号列を見つけよ。

問14　それ自身の随伴の反転をもたらすような記号列を見つけよ。

問15　それ自身の反転の随伴をもたらすような記号列を見つけよ。

問16　それ自身の随伴の反転の反復をもたらすような記号列を見つけよ。

問17　記号 Q と C だけを使った記号列で、それ自身をもたらすものはただ一つしかないことが証明できる。しかしながら、記号 Q、C、V だけを使った記号列で、それ自身をもたらすものはいくつも存在する。それは何種類あるだろうか。また、記号 Q、R、V だけを使った記号列で、それ自身をもたらすものは何種類あるだろうか。

問18　任意の記号列 y に対して、ある記号列 x で、x←y をもたらすものが存在することを証明せよ。たとえば、どのような記号列 x が x←JKL をもたらすだろうか。

（つづく）