はじまり。
存在することだけ注目されて具体的な構成がスルーされがちな万能帰納的関数さんですが、その基本性質として知られている s-m-n theorem (パラメータ定理) の証明には万能帰納的関数の具体的な構成を用いるのが普通です。そのため万能帰納的関数の存在をファクトにしてしまう本では s-m-n の証明も省略されてしまい、結果として読者は再帰定理や Rice の定理といった強力な s-m-n の系たちを「なんか成り立つらしい」で飲み込まなくてはなりません。
ちょっと待って!
証明が省略されて「成り立つよ」なんて納得できないですよね?納得できないので反例を出しました。s-m-n、再帰定理、Rice、そういうのが成り立たない残念な万能帰納的関数の例です。そんなに難しい例でもないので「私も出せるよ」と思いながら気楽に読むといいと思います。
前提知識
まずは些細な定義の違いで揉めたり疑問を残したりしないように、各用語が何を指すのかの共通認識を得ましょう。何事においても重要なことです。ただし帰納的関数の定義などは仮定します。
ゲーデル関数
自然数に対しで番目の素数を表すことにする。例えばなど。
このとき関数をゲーデル関数と呼ぶ。また始域を制限した を と書くことにする。
本当は、ゲーデル関数というのは特別ないくつかの条件を満たす関数ならなんでもよい、言わば関数の性質を表す言葉なのですが、ここでは詳しい解説を省くため特に性質の良い例である上の関数で固定しておきます。これは有限長の数列を自然数にコーディングするものです。
万能帰納的関数, universal recursive function
自然数上の二変数部分関数 が万能帰納的関数であるとは、任意の帰納的関数を実行できる帰納的関数であることを言う。つまり 自身が帰納的関数であり、さらに任意の帰納的関数に対し、のコードもしくはインデックスと呼ばれるある自然数が存在して なる関数が に一致する。
万能帰納的関数とはつまりコンピュータのことです。プログラム と入力 を受け取って、その実行結果 を得ます。コンピュータの内部実装がただ一つではないように、万能帰納的関数もその定義を満たす範囲で色々なものが考えることができます。これが今回の本題に繋がります。
s-m-n
を万能帰納的関数とする。このとき任意の自然数に対し、ある原始帰納的関数 が存在して、任意のに対し次を満たす。
これはプログラムに入力の一部を部分適用した新たなプログラムを計算できることを主張しています。あたかも任意の万能帰納的関数で成り立つかのように書いてありますが、成り立たない例も存在するよというのが今回の話です。
再帰定理
を万能帰納的関数とする。任意の一変数全域的帰納的関数 と自然数について、ある自然数が存在してとは同じ変数関数のコードになる。つまり と は同じ関数になる。
Rice
を万能帰納的関数とする。このとき、以下の条件全てを満たす関数は存在しない。
- 全域的である。
- 定数関数ではない。
- 帰納的関数である。
- ある自然数が存在し、同じ変数関数のコードとなる自然数には同じ値を返す。つまり、とが同じ関数ならばとなる。
再帰定理は一種の不動点定理です。s-m-n を使ってうまく具体的なを構成することで証明できます。また Rice は決定不能な集合をどんどん見つけることができる強い定理であり、条件1.2.3.と再帰定理をうまく使って条件4.に違反させることで証明できます。
お話。
万能帰納的関数の例 を具体的に構成したり、その構成で得られた において上の定理たちが成立することは自分で勉強してもらうとして、言葉の共有が済んだので本題に近づきましょう。
任意の万能帰納的関数 と0でない自然数について、次の集合は決定不能である。
決定可能であると仮定すれば、次の関数は全域的かつ帰納的。
よってこの関数のコードを考えれば、
より矛盾である。
今、対角線論法によって証明を行いましたが、Rice の定理を用いればの場合も含めてより簡単に示すことができます。
ちょっと待って!
でも0変数関数ってつまり定数なので、例えばのコードは、未定義関数のコードはという簡単なコーディングができてしまいますよね?そしてこの場合、に他ならず明らかに決定可能です。おっ、楽しいね。
本題
本題
任意に万能帰納的関数 をとる。このとき次の関数 も万能帰納的関数だが、Riceの定理は成立しない。
はい、Rice が成り立たない例が出ました。Rice は再帰定理から、再帰定理は s-m-n から従うので、もうこの時点で「再帰定理も s-m-n も壊れちゃったなぁ」という感じなのですが、ちゃんとどこがどうして壊れたのか眺めることは大切です。
s-m-n theorem に注目しましょう。一体どんな で困ってしまうでしょうか。もちろん0を使いたいのですが、では恒等関数がの例になってしまいます。ではの場合を考えましょう。このとき は次のような関数でなくてはなりません。
つまりは変数の数を固定しただけの万能帰納的関数、それも全域的であるという強力な代物というわけです。このような関数は当然、原始帰納的であるどころか帰納的ですらありません。
上の が帰納的であると仮定する。このとき
なる関数も全域的かつ帰納的だが、そのコードを考えれば
より矛盾である。
おわり。
今回挙げた例では、の場合は残念ながら、元の で s-m-n が成立するならその が必ず に対しても の条件を満たします。お?今度はで が存在しないような万能帰納的関数を探してみたくなってきましたね。なれ!その場合、今回のの代わりにどのような集合が Rice を破るのでしょうか?是非みなさん面白い例を出して私に教えてあげましょう。