不動点パズル21：不動点原理

（前回はこちら）

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

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

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

そして、この不動点原理は、

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

という。

今回の問題は、その不動点原理の証明である。

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

（解答）
これまで問題を解いてきて、よく使った記号列があった。それは、CQyC と RQyRQ である。CQyC は yCQyC をもたらし、RQyRQ は yRQyRQ をもたらす。ともに、x → yx となるような記号列で、CQyC は、記号Q と C、そして y に含まれる記号だけを使った記号列であり、RQyRQ は、記号Q と R、そして y に含まれる記号だけを使った記号列である。おそらくはこれらを使うことになるだろう。

また、話が前後してしまうが、特殊記号列についてあらためて確認しておこう。これまでに見た規則をあらためて確認すると、規則Q、C、R は以下である。

規則Q　任意の記号列 x に対して、記号列 Qx は x をもたらす
規則C　x が y をもたらすならば、Cx は y の随伴 yQy をもたらす
規則R　x が y をもたらすならば、Rx は y の反復 yy をもたらす

特殊記号列について確認したときに、規則Q と規則C から以下のことがいえるとした。

任意の記号列 x に対して、CQx は C(x)（すなわち xQx）をもたらす

C の不動点は、CCQCC である（「不動点パズル02」問２参照）。

同様に、規則Q と規則R からは、

任意の記号列 x に対して、RQx は R(x)（すなわち、xx）をもたらす

といえる。R の不動点は、RCQRC である（「不動点パズル05」問５参照）。

同様の表現で特殊記号列Θについて述べると、

任意の記号列 x に対して、ΘQx は Θ(x) をもたらす

といえる。ならば、Θの不動点は、ΘCQΘC となるのではないか。

と、まあ、ここまでは証明ではなく、単なる予想である。

さて、特集記号列は「記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす」という性質をもつ。ここで、ある記号列 y をΘ(x) と表すことにしている。この性質から、規則C や 規則R のような表現にすることも可能である。（便宜上、「規則Θ」と名付ける。）

規則Θ　z が x をもたらすならば、Θz はΘ(x) をもたらす

問いは、アーニーの不動点原理を証明することであった。与えられた特殊記号列Θに対して、そのΘの不動点となる記号列を見つけるということである。

これまでと同じようなやり方でやってみよう。

求める記号列（Θの不動点）を x とする。不動点の定義より、

x → Θ(x)　・・・・・①

となる記号列をさがす。

規則Θを使うため、x はΘからはじまる記号列として、x = Θz とすると、①は、

Θz → Θ(Θz)　・・・・・①'

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

z → Θz　・・・・・②

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

ここで、CQyC → yCQyC の y をΘとすると、CQΘC → ΘCQΘC で、②を満たす。このとき z = CQΘC である。

したがって、求める記号列 x は、

x = Θz = ΘCQΘC
∴特殊記号列Θに対して、そのΘの不動点 ΘCQΘC が存在する

同様に、RQyRQ → yRQyRQ を使うと、ΘRQΘRQ が得られる。

（つづく）