不動点パズル20：不動点

（前回はこちら）

さて、いよいよ「不動点」の登場である。アーニーの言葉を引用しよう。

「よろしい。ここで、x がΘ(x) をもたらすならば、x をΘの不動点という。ここまでに出題した問題の多くは、不動点を見つけるという問題の単なる言い換えにすぎない。……（中略）……。しかしながら、これらをすべてひとまとめにして一般化できるのだ」

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

これまでの問題には、次のような問題があった。たとえば、問２は、

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

というものである。

これを僕は「x → xQx となるような記号列 x を探す」というように解いていった。前回、特殊記号列のところで、Θ(x) という表記を見たが、それを使うと、「x → C(x) となるような記号列 x を探す」と言い換えることができる。C(x) をもたらす x を探すというのは、「C の不動点を見つける」ということの言い換えにすぎない。問３の「それ自身の随伴の随伴をもたらすような記号列を見つけよ」は、「CC の不動点を見つけよ」ということだし、「それ自身の随伴の反転の反復をもたらすような記号列を見つけよ（問16）」は、「RVC の不動点を見つけよ」ということである。

そして、アーニーの不動点原理は「すべての特殊記号列Θは不動点をもつ」という。

「さらに規則を追加して、より多くの記号列が特殊記号列になったとしても、不動点原理は依然として成り立つ。処理系に規則Q と C があれば、そのほかにどんな規則があっても、この原理に従う。また、処理系に規則Q と R があれば、そのほかにどんな規則があっても、この原理に従う。すなわち、任意の特殊記号列Θに対して、記号Q と C にくわえてΘに含まれる記号だけ、または記号Q と R にくわえてΘに含まれる記号だけを使ったΘの不動点が存在する」

問25　アーニーの不動点原理を証明せよ。与えられた特殊記号列Θに対して、そのΘの不動点となる記号列を見つけよ。これには2種類の解がある。一つは、記号Q と C、そしてΘに含まれる記号だけを使うもので、もう一つは、記号Q と R、そしてΘに含まれる記号だけを使うものだ。

（つづく）