不動点パズル23：二重不動点原理（試行錯誤）

（前回はこちら）

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

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

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

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


（試行錯誤）
これまでと同様のやり方でやってみる。

二つの記号列 x と y で、x は y の反復をもたらし、y は x の反転をもたらすので、

x → yy　・・・・・①
y → x←　・・・・・②

を満たす x と y を探す。

①は反復のかたちをしているので x = Rx₁、②は反転のかたちをしているので y = Vy₁ とすると、①②はそれぞれ、

Rx₁ → Vy₁Vy₁　・・・・・①'
Vy₁ → [Rx₁]←　・・・・・②'

と書ける。このとき、規則R、規則V の条件より、

x₁ → Vy₁　・・・・・③
y₁ → Rx₁　・・・・・④

とならなければならない。

さて、ここからどうするか……。一旦ここでやめておこう。

総当りで探す手はあるが、『スマリヤンのゲーデル・パズル』の本には二重不動点原理の導出のガイドとなる問題が出ているので、それらを順に解いていこう。

そのガイドとなる問題は以下である。

問27　規則Q と C だけを使い、それぞれが互いにもう一方をもたらすような二つの相異なる記号列を見つけよ。

（つづく）