不完全性定理(1) - エレファント・ビジュアライザー調査記録

『不完全性定理とはなにか (ブルーバックス)』という本を見ると、不完全性定理について調べるためのヒントがいろいろ書かれていたので少し調べてみようと思います。また、ビジュアルプログラミングで何かやる例にすることができるかもしれないと考えています。

この本では「不完全性定理」は「チューリング機械の停止問題」と同様に考えることができるという主張のようなので、まず「チューリング機械の停止問題」を考えてみます。

この本では「万能チューリング機械」を無限のメモリーを持つコンピューターで動くプログラミング言語と考えればわかりやすいということのようです。この本ではプログラミング言語BASICで説明されていますが、ここではプログラミング言語Cで説明しようと思います。「チューリング機械」をプログラミング言語Cのようなプログラミング言語の関数と考えます。「万能チューリング機械」をちゃんと定義すると長くなるので入門書では省略されていて、そのためにわかりにくくなっている場合が多いですが、この本でもわかりにくくなっているように思います。

この本では入力と出力があるBASICのプログラムを考えていますが、ここではCの引数と戻り値がある関数を考えます。
この本では(BASICのプログラムで)少なくともWHILEループを使うことができて、無限ループを書くことができるようになっていますが、ここで(Cの)whileループを使うことができて、無限ループを書くことができるとします。

関数の実行は一定の有限の時間で行われる「段階」の分けることができて、各「段階」では代入、分岐、ループのためのジャンプなどが行われます。各「段階」は通常は順に実行されますが、ジャンプによって指定した「段階」に移動することもあります。有限個の「段階」でreturnステートメントに到達して値を返却したとき関数は終了します。そうではないとき(無限ループに入ったとき)関数は終了しません。関数が終了しないとき関数の値は $\bot$ とします。

無限のメモリーを持つコンピューターで動くプログラミング言語の関数を考えます。このプログラミング言語は、プログラミング言語Cのようなプログラミング言語で、任意の個数の変数を持ち、任意の桁数の自然数を表すことができるとします。このプログラミング言語をプログラミング言語ωと呼ぶことにします。これは、もし無限のメモリーがあるなら通常のプログラミング言語Cでも成り立ちます。

このプログラミング言語ωの、引数がすべて自然数で、戻り値も自然数である関数を考えます。複数の自然数を一つの自然数にまとめることは可能で、そのまとめた自然数を元の複数の自然数に復元することも可能なので、引数の個数は1個のものを考えます。引数が複数の場合は、その複数の引数をまとめて一つの引数とし、それを元の複数の自然数に復元すると考えます。引数が複数のとき $(x_1, x_2, \cdots, x_n)$ のように「組」の形で書くこともできるとします。

「Cで書いたCの処理系」がありますが、それと同様にωでωの処理系を書きます。ωで書いたωの処理系をちゃんとした定義で書いたバージョンを、万能チューリング機械と考えることができます。ωで何ができるのかは説明していないのでCをイメージして想像することになります。

ωの関数 $f$ のはコンピューターのメモリー上では一つの自然数で表されます。この自然数を $\overline{f}$ と書くことにします( $f$ のコードと呼ぶことにします)。関数 $f$ を引数 $x$ で実行したときの戻り値があるとき、その戻り値を $f(x)$ と書くことにします。戻り値がないときは $f(x)$ を $\bot$ と書くことにします。

関数は「ソースコード」(文字列)で表されているとします。任意の文字列は「構文解析」によって「ソースコード」かどうかを判定することができるとします。関数の引数、変数名、数値は「リスト」になっているとします。

停止問題

この本の流れに沿って見ていきます。少しわかりにくいところがあると思われます。

【ステップ1】あらゆる計算にそれぞれ特化したチューリング機械 T に背番号(添え字)をつけて縦に並べる

関数のソースコードから「構造の『深さ』に関する帰納法」によって関数に番号をつけることができます。無限個使うことができる変数名、数値はリストで表されているので、これは可能です。逆に番号を指定すると、構造を再現することができます。番号 $i$ に対応する関数を「 $i$ 番目の関数」 $e(i)$ とします(この本の表記では $T_i$ ですが $i$ の関数になっていることを強調するためにこのように書くこともできるものとします)。

【ステップ2】T に入力できるデータ(1、2、3、…)を横に並べる

【ステップ3】各チューリング機械に1、2、3、…を入力した出力結果(または「計算が終わらない」ことを意味する疑問符)を一覧表にする

疑問符は $\bot$ の意味です。任意の一つのチューリング機械に任意の一つの自然数を入力したとき、停止するかどうかは決まっていると仮定します。これは仮定で、これを仮定するとどうなるのかを議論します。

この本によると、この表が表すチューリング機械を万能チューリング機械と呼びます。表の縦軸と横軸の2つの引数が必要ですが、2つの引数を1つにまとめることが可能なので、この表をチューリング機械と考えることができます。「 $i$ 番目の関数」 $e(i)$ の引数が $n$ のときの値 $e(i)(n)$ の引数をまとめた $e(i, n)$ (または $e( (i, n) )$ )を万能チューリング機械とみなします。

【ステップ4】表の対角線の各出力を変える。たとえば「1を足す」ことにしよう。ただし、計算が終わらない場合は「0」に変えることにする。この結果を与えるチューリング機械を D と呼ぶことにする。

【ステップ5】ステップ4で作ったチューリング機械も、チューリング機械である以上、一覧表のどこかにあるはずだが、それは $T_1$ ではない。なぜなら $T_1$ に1を入力した結果が異なるから。同様に、それは $T_2$ でもないし、 $T_3$ でもないし…一覧表のどこにも載っていない！

【ステップ6】チューリング機械 D がチューリング機械の一覧表に載っていない矛盾は、そもそもの仮定がまちがっていたからにほかならない。すなわち、任意のチューリング機械が停止するかしないかは決められないのである。

この本でこの後に書かれているように、このチューリング機械を $d$ として書き直します。任意の $x$ に対して $e(x,x)$ が停止するかどうかを判定することができると仮定すると、チューリング機械
$d(x) = \begin{cases} e(x,x)+1 & (e(x,x) \ne \bot) \\ 0 & (e(x,x) = \bot) \\ \end{cases}$
を定義することができます。このチューリング機械 $d$ は $e(1), e(2), \cdots$ の中にあります。これを $e(n)$ とすると、 $d(n) = e(n,n)$ となって $d$ の定義に矛盾します。よって $e(x,x)$ が停止するかどうかを判定することはできないことになります。

この本では「考え方はカントールの対角線論法と同じなので、ほとんどの読者が理解できたはずだ」と書かれていますが、

チューリング機械が停止するかどうかは決まっていると仮定して矛盾を導くという議論
チューリング機械はコンピューターのプログラムと考えれば良いと書かれているが、実際は万能チューリング機械の定義で数値からチューリング機械(プログラム)に変換しなければならないこと
万能チューリング機械の表の、チューリング機械の番号と数値を2つを入力とするチューリング機械を定義する方法

などのところがわかりにくいので簡単ではないです。