不動点パズル04：反復

（前回はこちら）

アーニーの機械は記号列を操作する機械で、ある記号列 x を入力すると、ある記号列 y をもたらす。この機械には2つの規則、規則Q と規則C がある。

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

任意の記号列 x に対して、xx という記号列を x の反復という。たとえば、記号列 HJK の反復は、HJKHJK である。


では、問題を見ていこう。

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

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

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

問８　それ自身の反復の反復、すなわち xxxx をもたらすような x を見つけよ。

問９　それ自身をもたらすような x があることはすでに分かっており、それは記号QとCから作られたものであった。しかし、記号Cを使わない別の記号列で、それ自身をもたらすものがある。そのような記号列を見つけよ。

問10　RQx が x の反復をもたらすことは分かっている。記号列 x で、Rx が x の反復をもたらすものは存在するだろうか。

問11　Ax をもたらす記号列 x として CQAC がある（すなわち CQAC が ACQAC をもたらす）ことは分かっている。記号 Q、R、A だけを使った別の記号列xで、Ax をもたらすものがある。このような x を見つけよ。より一般的には、任意の記号列 y に対して、記号 Q、R と y に含まれる記号だけを使った記号列 x で、yx をもたらすものが存在する。このような x を見つけよ。

＊＊＊＊＊

問１～４でわかったことを再掲しておく。

規則CQ　CQx → xQx（ x の随伴）
（任意の記号列 x に対して、記号列 CQx は x の随伴 xQx をもたらす）
CQC は、それ自身をもたらす

規則CCQ　CCQx → xQxQxQx（ x の随伴の随伴）
（任意の記号列 x に対して、記号列 CCQx は x の随伴の随伴をもたらす）　
CCQCC は、それ自身の随伴をもたらす

規則CCCQ　CCCQx → xQxQxQxQxQxQxQx（ x の随伴の随伴の随伴）
（任意の記号列 x に対して、記号列 CCCQx は x の随伴の随伴の随伴をもたらす）
CCCQCCC は、それ自身の随伴の随伴をもたらす

規則CQ-C　CQyC → yCQyC
（任意の記号列 y に対して、記号列 CQyC は yCQyC をもたらす）

（つづく）