万能帰納的関数に関する逆張り話。
ISer Advent Calendar 2020 12/01
はじまり。
存在することだけ注目されて具体的な構成がスルーされがちな万能帰納的関数さんですが、その基本性質として知られている s-m-n theorem (パラメータ定理) の証明には万能帰納的関数の具体的な構成を用いるのが普通です。そのため万能帰納的関数の存在をファクトにしてしまう本では s-m-n の証明も省略されてしまい、結果として読者は再帰定理や Rice の定理といった強力な s-m-n の系たちを「なんか成り立つらしい」で飲み込まなくてはなりません。
ちょっと待って！
証明が省略されて「成り立つよ」なんて納得できないですよね？納得できないので反例を出しました。s-m-n、再帰定理、Rice、そういうのが成り立たない残念な万能帰納的関数の例です。そんなに難しい例でもないので「私も出せるよ」と思いながら気楽に読むといいと思います。
前提知識
まずは些細な定義の違いで揉めたり疑問を残したりしないように、各用語が何を指すのかの共通認識を得ましょう。何事においても重要なことです。ただし帰納的関数の定義などは仮定します。
自然数$i$に対し$\mathsf{pr}(i)$で$i$番目の素数を表すことにする。例えば$\mathsf{pr}(0)=2, \mathsf{pr}(1)=3$など。
このとき関数$G:\bigsqcup_{i\in\mathbb{N}}\mathbb{N}^i\rightarrow\mathbb{N},(x_0,\dots,x_{n-1})\mapsto\prod_{i=0}^{n-1}\mathsf{pr}(i)^{x_i+1}$をゲーデル関数と呼ぶ。また始域を制限した $G|_{\mathbb{N}^i}$を $G^i$と書くことにする。
本当は、ゲーデル関数というのは特別ないくつかの条件を満たす関数ならなんでもよい、言わば関数の性質を表す言葉なのですが、ここでは詳しい解説を省くため特に性質の良い例である上の関数で固定しておきます。これは有限長の数列を自然数にコーディングするものです。
自然数上の二変数部分関数 $f:\mathbb{N}^2\rightharpoonup\mathbb{N}$が万能帰納的関数であるとは、任意の帰納的関数を実行できる帰納的関数であることを言う。つまり $f$自身が帰納的関数であり、さらに任意の帰納的関数$g:\mathbb{N}^n\rightharpoonup\mathbb{N}$に対し、$g$のコードもしくはインデックスと呼ばれるある自然数$e_g$が存在して $f(e_g,G^n(-))$なる関数が $g$に一致する。
万能帰納的関数とはつまりコンピュータのことです。プログラム $e_g$と入力 $(x_0,\dots,x_{n-1})$を受け取って、その実行結果 $g(x_0,\dots,x_{n-1})$ を得ます。コンピュータの内部実装がただ一つではないように、万能帰納的関数もその定義を満たす範囲で色々なものが考えることができます。これが今回の本題に繋がります。
$f$を万能帰納的関数とする。このとき任意の自然数$m,n\in\mathbb{N}$に対し、ある原始帰納的関数 $S^m_n:\mathbb{N}^{m+1}\rightarrow\mathbb{N}$が存在して、任意の$e,x_0,\dots,x_{n-1},y_0,\dots,y_{m-1}$に対し次を満たす。
$$ f(S^m_n(e,y_0,\dots,y_{m-1}),G^n(x_0,\dots,x_{n-1})) = f(e,G^{n+m}(x_0,\dots,x_{n-1},y_0,\dots,y_{m-1})) $$
これはプログラム$e$に入力の一部$y_0,\dots,y_{m-1}$を部分適用した新たなプログラム$S^m_n(e,y_0,\dots,y_{m-1})$を計算できることを主張しています。あたかも任意の万能帰納的関数で成り立つかのように書いてありますが、成り立たない例も存在するよというのが今回の話です。
$f$を万能帰納的関数とする。任意の一変数全域的帰納的関数 $g:\mathbb{N}\rightarrow\mathbb{N}$と自然数$k\in\mathbb{N}$について、ある自然数$u$が存在して$u$と$g(u)$は同じ$k$変数関数のコードになる。つまり $f(u,G^k(-))$と $f(g(u),G^k(-))$は同じ関数になる。
$f$を万能帰納的関数とする。このとき、以下の条件全てを満たす関数$g:\mathbb{N}\rightharpoonup\mathbb{N}$は存在しない。
- 全域的である。
- 定数関数ではない。
- 帰納的関数である。
- ある自然数$k\in\mathbb{N}$が存在し、同じ$k$変数関数のコードとなる自然数には同じ値を返す。つまり、$f(a,G^k(-))$と$f(b,G^k(-))$が同じ関数ならば$g(a)=g(b)$となる。
再帰定理は一種の不動点定理です。s-m-n を使ってうまく具体的な$u$を構成することで証明できます。また Rice は決定不能な集合をどんどん見つけることができる強い定理であり、条件1.2.3.と再帰定理をうまく使って条件4.に違反させることで証明できます。
お話。
万能帰納的関数の例 $f$を具体的に構成したり、その構成で得られた $f$において上の定理たちが成立することは自分で勉強してもらうとして、言葉の共有が済んだので本題に近づきましょう。
任意の万能帰納的関数 $f$と0でない自然数$k\in\mathbb{N}_{>0}$について、次の集合$\mathsf{total}_k\subset\mathbb{N}$は決定不能である。
$$ \mathsf{total}_k = \{e\in\mathbb{N}\mid f(e,G^k(-))は全域関数\} $$
決定可能であると仮定すれば、次の関数$g:\mathbb{N}^k\rightharpoonup\mathbb{N}$は全域的かつ帰納的。
$$
g(x_0,\dots,x_{k-1})=
\begin{cases}
f(x_0,G^k(x_0,\dots,x_{k-1}))+1 &(x_0\in\mathsf{total}_k) \\
0 &(otherwise)
\end{cases}
$$
よってこの関数のコード$e_g$を考えれば、
$$
g(e_g,\dots,e_g) = f(e_g,G^k(e_g,\dots,e_g))+1 = g(e_g,\dots,e_g)+1
$$
より矛盾である。
今、対角線論法によって証明を行いましたが、Rice の定理を用いれば$k=0$の場合も含めてより簡単に示すことができます。
ちょっと待って！
でも0変数関数ってつまり定数なので、例えば$n$のコードは$n+1$、未定義関数のコードは$0$という簡単なコーディングができてしまいますよね？そしてこの場合、$\mathsf{total}_0=\mathbb{N}_{>0}$に他ならず明らかに決定可能です。おっ、楽しいね。
本題
任意に万能帰納的関数 $f$をとる。このとき次の関数 $f'$も万能帰納的関数だが、Riceの定理は成立しない。
$$
f'(e,x) =
\begin{cases}
\mathsf{undefined} &(e=0\wedge x=G^0())\\
e-1 &(e>0\wedge x=G^0()) \\
f(e,x) &(otherwise)
\end{cases}
$$
はい、Rice が成り立たない例が出ました。Rice は再帰定理から、再帰定理は s-m-n から従うので、もうこの時点で「再帰定理も s-m-n も壊れちゃったなぁ」という感じなのですが、ちゃんとどこがどうして壊れたのか眺めることは大切です。
s-m-n theorem に注目しましょう。一体どんな $m,n\in\mathbb{N}$で困ってしまうでしょうか。もちろん0を使いたいのですが、$m=0$では恒等関数が$S^0_n$の例になってしまいます。では$m>0, n=0$の場合を考えましょう。このとき $S^m_0$は次のような関数でなくてはなりません。
$$ S^m_0(e,y_0,\dots,y_{m-1}) = \begin{cases} f(e,G^m(y_0,\dots,y_{m-1}))+1 &(f(e,G^m(y_0,\dots,y_{m-1}))が定義されている) \\ 0 &(otherwise) \end{cases} $$
つまり$S^m_0$は変数の数を固定しただけの万能帰納的関数、それも全域的であるという強力な代物というわけです。このような関数は当然、原始帰納的であるどころか帰納的ですらありません。
上の $S^m_0$が帰納的であると仮定する。このとき
$$
g(x_0,\dots,x_{m-1}) = S^m_0(x_0,x_0,\dots,x_{m-1})
$$
なる関数も全域的かつ帰納的だが、そのコード$e_g$を考えれば
$$
g(e_g,\dots,e_g) = S^m_0(e_g,e_g,\dots,e_g) = f(e_g, G^m(e_g,\dots,e_g))+1 = g(e_g,\dots,e_g)+1
$$
より矛盾である。
おわり。
今回挙げた例では、$m>0,n>0$の場合は残念ながら、元の $f$ で s-m-n が成立するならその $S^m_n$ が必ず $f'$ に対しても $S^m_n$ の条件を満たします。お？今度は$m>0,n>0$で $S^m_n$ が存在しないような万能帰納的関数を探してみたくなってきましたね。なれ！その場合、今回の$\mathsf{total}_0$の代わりにどのような集合が Rice を破るのでしょうか？是非みなさん面白い例を出して私に教えてあげましょう。