システム管理者
数値Ω
Ωの発見に向けた第一歩は、ライプニッツのエッセイが出版されてからちょうど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$$
［訳注）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やπのように正確に計算できるように見えますが、そうではありません。数値Ωは厳密に定義されており、非常に具体的な意味がありますが、実際には解決策がない停止の問題を解決するので、計算することはできません。具体的には、Ωの最初のN ビットを 知ることで、最大N ビットの長さのプログラムが停止するかどうかを判断できます。つまり 、ΩのNビット を見つけるには、少なくともN ビットの長さのプログラムが必要です。Ωで特定のビット数を定義できないことを示唆しているわけではないことに注意してください。たとえば、コンピュータプログラム 0、10、および110が停止することを知っていると、Ωの最初の3ビットまでと言えます。0.111の形式です。重要なのは、Ωの最初のNビットは、Nビットよりも大幅に短いプログラムを使用して計算できないということです。
最も重要なことは、 Ωが無限の数の還元不可能なビットを与えることです。有限の長さのプログラムは、何十億ビットも含まれていても、残りのビットを決定するのに役立ちません。残りのビットは無限にあります。言い換えれば、公理の有限集合に対して、この集合を使用して証明できない真実の数は無限です。
数値Ωが非圧縮であるのはなぜか？
数値が非圧縮であること、つまり、最初の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であろうと）である。このように、数学の複雑さは無限であるのに対し、「世界の万物」のいかなる個々の理論も有限の複雑さを特徴とし、その結果、数学的真理の世界の豊かさをすべてカバーすることはできない。これまで言われてきたことから証明に意味がないということではありませんし、私は決して論理的な推論に反対しているわけではありません。実際、説明不能な原理（公理）は、常に数学の一部である。Ωという数字を見ただけで、今まで考えられていたよりもはるかに多いことがわかります。
数学者は何でも証明しようとする必要はないのかもしれません。彼らは真実ではない事実については、新しい公理を追加するべきです。問題は、彼らが説明不能であることを理解し、証明できないことを認めることです。しかし、厳密な証明ではなく、常にもっともらしい推論を用い、新しい法則を導き出して新鮮な実験データを理解しようとする物理学者とは異なり、数学者は決してあきらめることはありません。数学は物理学に似ているのだろうか？
概要：還元不可能な複雑さ
＊ゲーデルは、数学にある不可避の不完全性を示しました。厳密に証明できない真の命題があります。特異数Ωはさらに大きな不完全性を明らかにし、有限の公理集合から推論できない定理が無数に存在することを証明しました。
＊Ωという数値は厳密に定義されており、非常に具体的な意味がありますが、有限のコンピュータプログラムを使用して計算することはできません。
＊数値Ωの特性の分析は、数学者が新しい公理を仮定する必要があることを示しています。これは、物理学者が実験の結果を一般化し、論理の助けを借りて証明できない基本的な法則を導き出すときに行うことです。
