投稿記事

証明可能性の限界(1)

投稿日時: 2020/10/29 システム管理者

https://elementy.ru/nauchno-populyarnaya_biblioteka/430319/Predely_dokazuemosti

グレゴリー・チェイチン
「科学の世界で」2006年第6号より

 

 

 

 

 

 

 

 

ゴットフリート・ライプニッツが、「形而上学の議論」(1686年)で、最初に表現した複雑さとランダム性の考え方と、現代の情報理論におけるそれらの確認から、数学が「すべての中で最も一般的な理論」を作ることは不可能です。

1956年、Scientific American誌は、Ernest NagelとJames R.Newmanによる記事「Gödel's Proof」を発表しました。2年後、その著者は同じ名前の本をリリースしました(まだ再版されています)。当時はまだ子供でしたが、ニューヨーク公立図書館で本を開いたときのスリルを今でも覚えています。

Kurt Gödelゲーデルが、数学を使って、数学自身の可能性の限界を示していることに私は驚いた。彼は、数学の完全な理論の存在についてDavid Hilbertヒルベルトが約1世紀前に行った命題に反論しました。数学的論理の規則を一貫して使用することにより、数学のすべての命題を導き出すことができる究極の公理系はあるか。ゲーデルは、この方法では証明できない真の数学的命題が存在することを示しました。彼の結論は、「この命題は誤りである」と「この命題は証明できない」という2つの自己関連のパラドックスに基づいています。(ゲーデルの不完全性定理の詳細については、 Scientific Americanを参照してください。)

 

 

 


有限のコンピュータプログラムを使用して、計算できない特定の厳密に定義された数Ωの存在は、真の命題を厳密に証明できる包括的な数学システムを作る希望を打ち砕きました。(画像:www.sciam.ru)

 

 

 

 

私は生涯を通じてゲーデルの証明を扱い、半世紀後、自分の本を出版しました。ある程度、これはNagelとNewmanネーゲルとニューマンの本の私のバージョンですが、ゲーデルの証明はその主要なテーマではありません。私の仕事は、情報を測定し、いくつかの数学的な事実は複雑すぎるために理論に詰め込むことができないことを証明することに基づいています。私のアプローチによると、ゲーデルは氷山の一角を発見しただけです。有限の公理体系からは証明できない正しい数学的定理が無数にあります。

複雑さと科学の法則

 

 

ライプツィヒに記念碑が建てられたゴットフリート・ライプニッツは、300年前にアルゴリズム情報の多くの特性を予見していました(www.uni-leipzig.deからの写真)

 

 

 

 

 

 

 

 

1686年、ライプニッツの哲学的エッセイDiscoursdemétaphysique形而上学の議論が出版されました。提起された問題は:特定の法則によって記述できる事実を、どの法則にも従わない事実からどのように区別するか?
彼のエッセイの4章で、ライプニッツは非常に単純で深遠な考えを表現しました。理論は、それが説明するデータよりも単純でなければなりません。そうでなければ、何も説明しません。科学法則の概念は、それが無制限のレベルの数学的複雑さを許容する場合、意味がなくなります。なぜなら、事実がどれほどランダムで乱雑であっても、法則を定式化することが常に可能だからです。逆に、一部のデータを説明する単一の法則が複雑すぎることが判明した場合、問題のデータは実際にはどの法則にも従いません。

アルゴリズム情報の現代の数学理論は、複雑さと単純さの概念の正確な定量的定義を与えることを可能にしました。従来の情報理論は、情報をエンコードするために必要なビット数によって情報量を定義します。たとえば、単純な「はい/いいえ」の回答をエンコードするには、1ビットが必要です。対照的に、アルゴリズム情報量は、データを生成するために必要なコンピュータプログラムの長さによって決定されます。プログラムを格納するために必要な最小ビット数は、アルゴリズムデータ情報量と呼ばれます。たとえば、自然数1,2,3,... の無限のシリーズには、アルゴリズム情報がほとんど含まれていません。シリーズのすべての数は、短いコンピュータプログラムを使用して取得できます。計算を完了するのにかかる時間や、使用するメモリ量は関係ありません。プログラムの長さ(ビット単位)のみが重要です。(もちろん、アルゴリズム情報量の正確な値は、選択したプログラミング言語によって異なりますが、この記事で説明する問題については、これは関係ありません。)

別の例として、3.14159...に等しい数πを考えてみましょう。そのアルゴリズム情報量は少ない:すべての符号を順次計算するには、かなり短いアルゴリズムですむ。しかし、100万文字のみを含むランダムな数値、たとえば1.341285 ... 64は、はるかに大量のアルゴリズム情報によって特徴付けられます。そのような数字には定義構造がないため、それを書き込むために必要なプログラムの長さは、数字自体の長さに近くなります。

 

 

科学理論は、観察結果を予測するコンピュータプログラムのようなものです。有用な理論は、実験データの昇華です。いくつかの法則と方程式を使用して、さまざまな現象の全世界を記述することができます(画像:www.sciam.ru)

 

 

(...で置き換えたすべての数字をプログラムに含める必要があります。)このような数字の列を計算できる短いプログラムはありません。プログラムは圧縮できず冗長性もありません。最善の方法は、そのまま書き出すので、このような列は、還元不可能またはアルゴリズム的にランダムと呼ばれます。

上記は科学法則や事実との関連は如何でしょうか?
アイデアは、プログラマーの目を通して科学を見ることです。科学理論は、観察の結果すなわち実験データを予測するコンピュータプログラムのようなものです。この見方は、2つの基本原則に基づいています。最初の(Occam's razor「オッカムのかみそり」)によると、いくつかのデータを説明する2つの理論のうち、より単純なものが優先されるべきです。言い換えれば、最良の理論は、観測結果を計算するための最短のプログラムです。ライプニッツによって示された2番目の原則は、現代の用語では次のように言います。ビット単位のサイズが説明するデータ量に等しい理論は、完全にランダムなデータを記述できるため、役に立ちません。有用な理論は情報の削減を提供します:データを理解することは、それらを短いアルゴリズムの説明に圧縮することです。理論が単純であるほど、現象の本質をよりよく理解できます。

十分な理由
コンピュータプログラム登場の2世紀半前に生きていたライプニッツは、現代のアルゴリズム情報の概念に非常に近づいていました。ライプニッツは、すべてがバイナリコードの形式で表現できることを知っており、最初のコンピューティングデバイスの1つを作成しました。複雑さと単純さの概念を考慮して、彼はコンピューティングの巨大な可能性を認識していました。ライプニッツが知っていたすべての要素を組み合わせていたとしたら、彼はおそらく自分の哲学の基礎の一つである十分な理由の原理(起こったものにはすべて理由がある)を疑っていただろう。ポジションが真であれば、何らか真の理由があります。しかし、日常の喧騒の中で、信じられないことが起こります。理由が常にわかるとは限りません(おそらく、推論の連鎖が長すぎて混乱しているため)、神のみぞ知る。それですべてです!

数学者は、常にすべてを証明しようと努力しているため、ライプニッツの十分な理由の原理を無条件に受け入れることは間違いありません。たとえ定理の真実が明白であり、何百万もの例がそれを確認したとしても、数学者は依然として一般化された証明を必要とします。そして、アルゴリズム情報の概念は、知識の出所と限界についての哲学的推論に驚くべき貢献をすることができます。それは、いくつかの数学的事実が理由もなく真実であることを示しており、十分な理由の原理に異議を唱えています。以下に示すように、還元不可能な数学的事実は無数にあり、その真実はいかなる理論によっても説明ができません。それらは計算上還元できないだけでなく、論理的にも還元できません。これらの事実を「証明」する唯一の方法は、理由なしでそれらを公理として認識することです。

「公理」の概念は、論理的な還元不可能性と密接に関連しています。公理は、私たちが自明であると考え、かつ単純な原理から証明できない数学的提案です。すべての数学理論は、公理から導かれる定理で、これは、ユークリッドが2000年前に行ったことです。幾何学に関する彼の著書は数学的な表現の手本になりました。

古代ギリシャでは、他の方法ではなく、この方法で投票するように仲間の市民を説得するために、あなたの理由を述べる必要がありました。これがおそらく、ギリシャ人が数学的な提案は証明されるべきであり、経験的に推論されるべきではないという考えに至った理由です。(ギリシャ人とは異なり、メソポタミアとエジプトの初期の文明は実験に依存していたようです。)論理的推論の方法は非常に実り多いことが判明しました。現代の数学、数学的物理学、そしてコンピュータ構築技術を含むすべての精密科学は、現代の数学と論理機械の助けを借りて作られました。
私は2千年かけて構築した数学とすべての科学のアプローチが失敗だったと主張しているのでしょうか? ある意味そうです。私の反論例は、論理と推論の限界を示し、証明できない数学的規則の無限の流れの源を、私が「オメガ」Ωと呼ぶ数に担わせることです。