不動点パズル15：回文

（前回はこちら）

機械に、ある記号列 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 の反転をもたらす）

さらに規則を導入する。

規則P　x → y ならば、Px → yy←
（x が y をもたらすならば、Px は 対称記号列 yy← をもたらす）

たとえば、x が ABC をもたらすならば、Px は ABCCBA をもたらす。xx← は対称記号列であり、前から読んでも後ろから読んでも同じ記号列となる。そのため対称記号列は、回文記号列とも呼ばれる。xx← を x の回文と呼ぶ。

回文記号列についての問題は、以下の3問。

問20　それ自身の回文 xx← をもたらすような x を見つけよ。

問21　x←x をもたらすような x を見つけよ。

問22　それ自身の随伴の回文をもたらすような記号列を見つけよ。

（つづく）