万能帰納的関数に関する逆張り話。

ISer Advent Calendar 2020 12/01

はじまり。

存在することだけ注目されて具体的な構成がスルーされがちな万能帰納的関数さんですが、その基本性質として知られている s-m-n theorem (パラメータ定理) の証明には万能帰納的関数の具体的な構成を用いるのが普通です。そのため万能帰納的関数の存在をファクトにしてしまう本では s-m-n の証明も省略されてしまい、結果として読者は再帰定理や Rice の定理といった強力な s-m-n の系たちを「なんか成り立つらしい」で飲み込まなくてはなりません。

ちょっと待って！

証明が省略されて「成り立つよ」なんて納得できないですよね？納得できないので反例を出しました。s-m-n、再帰定理、Rice、そういうのが成り立たない残念な万能帰納的関数の例です。そんなに難しい例でもないので「私も出せるよ」と思いながら気楽に読むといいと思います。

前提知識

まずは些細な定義の違いで揉めたり疑問を残したりしないように、各用語が何を指すのかの共通認識を得ましょう。何事においても重要なことです。ただし帰納的関数の定義などは仮定します。

本当は、ゲーデル関数というのは特別ないくつかの条件を満たす関数ならなんでもよい、言わば関数の性質を表す言葉なのですが、ここでは詳しい解説を省くため特に性質の良い例である上の関数で固定しておきます。これは有限長の数列を自然数にコーディングするものです。

万能帰納的関数とはつまりコンピュータのことです。プログラム $e_g$と入力 $(x_0,\dots ,x_{n-1})$を受け取って、その実行結果 $g(x_0,\dots ,x_{n-1})$ を得ます。コンピュータの内部実装がただ一つではないように、万能帰納的関数もその定義を満たす範囲で色々なものが考えることができます。これが今回の本題に繋がります。

これはプログラム$e$に入力の一部$y_0,\dots ,y_{m-1}$を部分適用した新たなプログラム$S_n^m(e,y_0,\dots ,y_{m-1})$を計算できることを主張しています。あたかも任意の万能帰納的関数で成り立つかのように書いてありますが、成り立たない例も存在するよというのが今回の話です。

再帰定理は一種の不動点定理です。s-m-n を使ってうまく具体的な$u$を構成することで証明できます。また Rice は決定不能な集合をどんどん見つけることができる強い定理であり、条件1.2.3.と再帰定理をうまく使って条件4.に違反させることで証明できます。

お話。

万能帰納的関数の例 $f$を具体的に構成したり、その構成で得られた $f$において上の定理たちが成立することは自分で勉強してもらうとして、言葉の共有が済んだので本題に近づきましょう。

今、対角線論法によって証明を行いましたが、Rice の定理を用いれば$k=0$の場合も含めてより簡単に示すことができます。

ちょっと待って！

でも0変数関数ってつまり定数なので、例えば$n$のコードは$n+1$、未定義関数のコードは$0$という簡単なコーディングができてしまいますよね？そしてこの場合、${\mathsf{total}}_0={\mathbb{N}}_{>0}$に他ならず明らかに決定可能です。おっ、楽しいね。

本題

はい、Rice が成り立たない例が出ました。Rice は再帰定理から、再帰定理は s-m-n から従うので、もうこの時点で「再帰定理も s-m-n も壊れちゃったなぁ」という感じなのですが、ちゃんとどこがどうして壊れたのか眺めることは大切です。

s-m-n theorem に注目しましょう。一体どんな $m,n\in \mathbb{N}$で困ってしまうでしょうか。もちろん0を使いたいのですが、$m=0$では恒等関数が$S_n^0$の例になってしまいます。では$m>0,n=0$の場合を考えましょう。このとき $S_0^m$は次のような関数でなくてはなりません。

$$S_0^m(e,y_0,\dots ,y_{m-1})=\{\begin{array}{ll}f(e,G^m(y_0,\dots ,y_{m-1}))+1& (f(e,G^m(y_0,\dots ,y_{m-1}))が定義されている)\\ 0& (otherwise)\end{array}$$

つまり$S_0^m$は変数の数を固定しただけの万能帰納的関数、それも全域的であるという強力な代物というわけです。このような関数は当然、原始帰納的であるどころか帰納的ですらありません。

おわり。

今回挙げた例では、$m>0,n>0$の場合は残念ながら、元の $f$ で s-m-n が成立するならその $S_n^m$ が必ず $f^{\prime }$ に対しても $S_n^m$ の条件を満たします。お？今度は$m>0,n>0$で $S_n^m$ が存在しないような万能帰納的関数を探してみたくなってきましたね。なれ！その場合、今回の${\mathsf{total}}_0$の代わりにどのような集合が Rice を破るのでしょうか？是非みなさん面白い例を出して私に教えてあげましょう。