不動点パズル22：二重不動点原理（プロローグ）

（前回はこちら）

アーニーが作った機械は記号列を操作する機械で、その機械にはいくつかの規則があるが、そこには「不動点原理」が存在することがわかった。

不動点原理
すべての特殊記号列Θは不動点をもつ。

特殊記号列
記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列を呼ぶ。

不動点
x がΘ(x) をもたらすならば、x をΘの不動点という。

さらに規則を追加して、より多くの記号列が特殊記号列になったとしても、不動点原理は成り立つ。機械（処理系）に規則Q と C があれば、そのほかにどんな規則があっても、不動点原理に従う。また、処理系に規則Q と 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 の反復をもたらす）

アーニーはさらに、「二重不動点原理」があるという。

二重不動点原理
任意の特殊記号列Θ₁ とΘ₂ に対して、x がΘ₁(y) をもたらし、y がΘ₂(x) をもたらすような記号列 x と y が存在する。

この二重不動点原理がわかっていれば、次の問題が解けるという。

問26　二つの記号列 x と y で、x は y の反復をもたらし、y は x の反転をもたらすようなものを見つけよ。

現時点では、二重不動点原理がわかっていない状態なので、問26は解けない可能性が高い。しかし、わからないかもしれないが、まずはやってみよう。

（つづく）