証明可能性の限界（２）

数値Ω
Ωの発見に向けた第一歩は、ライプニッツのエッセイが出版されてからちょうど250年後に出た有名な論文でした。1936年、ロンドン数学協会プロシーディングズに、アラン・チューリングは単純なユニバーサルコンピューティングマシンの数学モデルを発表しました。さらに、彼はコンピュータプログラムが停止するか否かの判断が可能かどうか疑問を持ちました。これが有名な停止問題の定式化でした。

数値Ωは、未知な数学部分を表しています。有限長のコンピュータプログラムは、この数の有限のビットしか決定できません。後続のビットはすべて、未知な暗闇の中に残ります（画像：www.sciam.ru）

もちろん、プログラムを実行すると、最終的には停止していることに気付く場合があります。基本的な問題は、プログラムが停止しない場合に、いつあきらめて停止するかを決定することです。多くの特殊なケースでは解決できますが、チューリングは一般的な解決策がないことを示しました。アルゴリズムも数学理論も、どのプログラムが停止し、どのプログラムが停止しないかを決定することはできません。（このチューリング問題の近代的な証明は、サイエンティフィック・アメリカンのウェブサイト上で見つけられます。）ちなみに、私は現代的な意味で「プログラム」という言葉を使用していて、それはコンピュータプログラム自体と、それが処理するデータを意味しています。

数値Ωに向けた次のステップは、考えられるすべてのプログラムの集合を検討することです。ランダムに選択されたプログラムが停止することはありますか？停止確率は Ωです。まず、プログラムをランダムに選択する方法を決めましょう。プログラムはビットの列であるため、後続の各ビットの値を選択するには、単にコイン投げをします。プログラムには何ビットを含める必要がありますか？コンピューターが次のビットを要求しなくなるまで、コイン投げを繰り返します。数値 Ωは、このようなランダムなビット列が導入されたときに、マシンが停止する確率です。（数値Ωはプログラミング言語の選択に依存しますが、この数の驚くべき特性はプログラム言語によりません。言語を選択すると、Ω はπや5のような特定の数値をとり ます。）

数値Ωは確率を表すため、 ゼロより大きく、1より小さい必要があります。あるプログラムは停止し、あるものは停止しません。バイナリコードで記述されたΩの数は 0.1110100...のようになり、小数点以下のビットの列は還元不可能であり、それ自体も還元不可能な数学的実態であることがわかります（実態の各ビットは0か1かです）。

Ωの決定方法

数値Ωがどのように決定されるかを理解するために、簡単な例を考えてみましょう。特定のコンピュータのすべてのプログラムのうち、停止するのは3つだけで、それぞれ、110，11100，11110，これらの長さは、それぞれ3，5，5，ビットであるとします。我々はランダムに連続する各ビットの値を決定するためにコインを投げ、それら各ビットの状態実現確率は1/2です。各プログラムの確率は、1/2^{3}, 1/2^{5}, 1/2^{5}, です。次に、そのようなコンピューターのプログラムを停止する確率は、次の式によって決定されます。

Ω=1/2^{3}+1/2^{5}+1/2^{5}=0.001+0.00001+0.00001=0.00110
［訳注）この式の途中で，10進数表記が2進数表記に変わっています．1/2^{3}は10進数表現，0.001は2進数表現です．他の項も同様］

ここで、2進数は、3つの停止プログラムの1つをランダムに選択する確率を表します。プログラム110が停止するので、1100や1101など、110で始まる3ビットより長いプログラムは考慮しません。したがって、それぞれの合計に0.0001を追加していません。

このように始めにプログラム110が含まれる長いプログラム（1100など）のすべては，停止すると見なします。言い換えると、プログラムデータは停止した後、それ以上のビットを要求しないので自己制御的です。

数Ωは無限和として定義することができ 、長さがNビットの各プログラムは、Ωに1/2^{N}だけ寄与します。言い換えると、停止するNビットの各プログラムは、数Ωのバイナリ表現のN番目のビットに1を加算する。

停止しているプログラムに対応する全てのビットを加算することで、正確なΩの値を得ることができます。数Ωは√2やπのように正確に計算できるという印象を受けます。しかし、これはそうではありません：数Ωは厳密に定義されており、かなり具体的な値を持っていますが、それを計算することは不可能です。より具体的には、数Ωの最初のＮビットを知ることにより、Ｎビット長までのプログラムが停止しないかどうかを判断することが可能となり、数ΩのＮビットを見つけるためには、少なくともＮビット長のプログラムが必要となる。私は、数Ωのあるビット数を決定することは不可能だと主張しているのではありません。例えば、コンピュータプログラム０、１０、１１０が停止することを知っていれば、最初の３ビットの精度でΩが0.111であることがわかる。Ωの最初のＮビットは、Ｎビットよりも大幅に短くなるようなプログラムでは計算できないという事実です。
一番重要なのは、Ωが無限に未計算のビットを与えてくれることです。どんな有限長プログラムでも、それが何十億ビットを含んでいようと、無限にある残りのビットを決定することはできません。言い換えれば、任意の有限の公理の集合では、この集合では証明できない真理が無限に存在することになります。

数値Ωが非圧縮であるのはなぜか？

数値が非圧縮であること、つまり、最初のNビットがNビットより短いプログラムで決定できないことを証明してみましょう。チューリングの停止問題に照らして、Ωの特性を分析しましょう。Nビット長までのプログラムは、それより短いプログラムでは問題を解決できないという命題を使用します。

Ωの非圧縮性を実証するために、最初のNビットを知ることで、Nビットまでの長さのプログラムのチューリング問題を解くことができることを示します。N ビット以下の長さのプログラムでは、Ωの最初の N ビットを計算できないことがわかります。(もしそのようなプログラムが存在するならば、その助けを借りて、最初のNビットΩを計算して、Nビットの長さのプログラムのチューリング問題を解くのに使うことができます。)

それでは、ΩのNビット知ることで、停止問題を解くことができ、Nビット長までのプログラムのうち、どのプログラムが停止するかを決定することができるかを見てみましょう。一歩一歩やっていきましょう。Ｋステップでは、各プログラムをＫ秒間実行し、停止したプログラムの数によって、停止する確率Ω_{K}を決定します。Ωが全てのプログラムを用いて算出されるのに対し、最終的に停止するプログラムのサブセットのみを用いて取得されるため、Ωよりも小さいが、Ｋが増加するにつれて、Ω_{K}の値はΩに近づき、Ω_{K}の最初のビットの多くがΩの対応するビットと等しくなります。 Ω_{K}とΩの最初のNビットが一致する場合、これは、Nビット長までのすべてのプログラムが考慮され、遅かれ早かれ停止することを意味します。

(他にもNビット長のプログラムがあったとしたら、後段Kで停止してしまい、Ω_{K}がΩよりも大きくなってしまうので、あり得ない)。

つまり、Ωの最初のNビットを知ることで、Nビットまでの長さのすべてのプログラムの停止問題を解くことができます。今、Ωの最初のNビットの長さがNビットよりも有意に短いプログラムで検出できるとしましょう。そして、Ω_{K}を計算するプログラムと組み合わせて、Ｎビット以下のプログラム長を求めることで、Ｎビットまでのすべてのプログラムの停止問題を解決することができるが、上記のように、そのようなプログラムは存在し得ない。したがって、Ωの最初のＮビットを計算するためには、ほぼＮビットの長さのプログラムが必要となる。これは、数Ωが非圧縮性であること、すなわち、適用できないことを認めれば十分である。(大きなNビットの場合、NビットからほぼNビットへの長さ短縮は重要ではありません)。

Ωという数が受け入れられないことから、包括的な数学的理論が存在し得ないことは、次のとおりである。無限のビット数Ωは、ビット列よりも単純な、いかなる原理からも導き出すことのできない数学的事実の無限集合（選択された各ビットが１であろうと0であろうと）である。このように、数学の複雑さは無限であるのに対し、「世界の万物」のいかなる個々の理論も有限の複雑さを特徴とし、その結果、数学的真理の世界の豊かさをすべてカバーすることはできない。これまで言われてきたことから証明に意味がないということではありませんし、私は決して論理的な推論に反対しているわけではありません。実際、説明不能な原理（公理）は、常に数学の一部である。Ωという数字を見ただけで、今まで考えられていたよりもはるかに多いことがわかります。

数学者は何でも証明しようとする必要はないのかもしれません。彼らは真実ではない事実については、新しい公理を追加するべきです。問題は、彼らが説明不能であることを理解し、証明できないことを認めることです。しかし、厳密な証明ではなく、常にもっともらしい推論を用い、新しい法則を導き出して新鮮な実験データを理解しようとする物理学者とは異なり、数学者は決してあきらめることはありません。数学は物理学に似ているのだろうか？

概要：還元不可能な複雑さ
＊ゲーデルは、数学にある不可避の不完全性を示しました。厳密に証明できない真の命題があります。特異数Ωはさらに大きな不完全性を明らかにし、有限の公理集合から推論できない定理が無数に存在することを証明しました。

＊Ωという数値は厳密に定義されており、非常に具体的な意味がありますが、有限のコンピュータプログラムを使用して計算することはできません。

＊数値Ωの特性の分析は、数学者が新しい公理を仮定する必要があることを示しています。これは、物理学者が実験の結果を一般化し、論理の助けを借りて証明できない基本的な法則を導き出すときに行うことです。