1.1 原理的な極限と資源的な極限
計算可能性理論は決定的な区別を導入します。原理的には計算可能だが実際には解くことができない問題があり、原理的には非計算可能な問題、つまり有限のステップ数ですべてのケースで正しい答えを与えるチューリングマシンがない問題があります。チューリングの停止問題は典型的です。プログラムがプログラムと任意の入力について、そのプログラムが停止するか無期限に実行を続けるかを決定する一般的なアルゴリズムは存在しません。
ゲーデルの貢献は形式体系の領域で類似しています。十分に表現力のあるシステム(例えば算術)では、システム内で証明可能ではない真の陳述が存在するでしょう。数学の「純粋」領域においてさえ、真実であるものすべてが証明可能であるわけではなく、よく定式化されたすべての問題が決定的なアルゴリズムを認めるわけではありません。
別の規模で、別のタイプの極限が現れます。計算可能だが計算時間またはエネルギーが実際に到達不可能にする問題。計算は論理的プロセスだけではなく、物理的プロセスでもあります。Landauerが示したように、各取り返しのつかない論理的操作はエネルギーを散逸させます。計算可能なものの極限は論理的でも実践的なものでもありません。それは物理的です。
1.2 宇宙はチューリングマシンか?
強い仮説は次のようなものでしょう。宇宙が本質的に計算可能なシステムであれば、その状態と進化は数学的計算可能性の極限に類似した極限に従うでしょう。その方向への提案があります。細胞オートマトン模型から、物理的進化を分散計算と同じと考えるアプローチまで。しかし、このステップは自明ではありません。宇宙が完全に計算可能であることは証明されていません。連続性、一般相対論、量子力学の特定の側面は、標準的な離散計算モデルに還元不可能な現象の可能性を開いたままにします。
ロジャー・ペンローズのような著者は正反対を論じています。アルゴリズム的に捉えられない数学的真実の存在は、人間の心と現実のある側面は単なる計算ではないことを示唆するだろう、と。彼の論文は異議を唱えられていますが、よい主張をしています。何らかの厳密さなく「現実」を「アルゴリズム」と同じにすることは、かなり多くの正当化を必要とする外挿です。
物理系が古典的な計算体系のように振る舞うどこでも、チューリングとゲーデルのような計算可能性の極限に類似した極限が現れるでしょう。しかし、それは現実のすべてを理解しません。宇宙はチューリングマシンに還元不可能な層を含むかもしれません。
1.3 カオス、気候、および不確実性のタイプ
計算可能性を超えて、利用可能な情報と系のタイプに関連する極限があります。気候のようなカオス的系では、初期条件のわずかな変化は指数関数的に増幅されます。方程式は決定論的かもしれませんが、初期測定でのエラーは中期の実用的な不予測性に変換されます。
二つのタイプの不確実性を区別する必要があります。アレアトリーン不確実性はデータの欠如または不正確な測定が原因であり、原理的には減らすことができます。カオス的不確実性は構造的です。非常に正確なデータでさえ、系の構造はわずかな不正確さが増幅されて予測地平線に確定的になるまで作られます。データを追加してもこの不確実性は排除されません。予測の影響を予測地平線に遅延させることだけができます。
1.4 複雑性:計算可能だが物理的に実行不可能
いくつかの問題は決定可能ですが、計算時間は非常に速く増加するため、可能な物理系はそれを時間とエネルギーが尽きる前に完了することはできません。NP完全問題の特定のインスタンス、多くの体の量子系の正確なシミュレーション、そして天文学的な組み合わせ空間での徹底的な探索はすべてこれを実証します。宇宙の年齢より多くの年を必要とする手続きは、実用的な目的では実現不可能なものと同等です。
1.5 数学:形式的なものと実践の間
数学は極限の議論で奇異な場所を占めています。一方では、完全に形式化可能な領域のように見えます。他方では、実際の数学的慣行は還元不可能な緊張を明らかにします。数学者は形式的なマシンのように動作しません。彼らは直感、数値的実験、視覚化、試行錯誤を使用します。「証明」と見なされるものは完全に構文ルールで固定されていません。コミュニティ判断、伝統、変化する基準のコンポーネントがあります。
ここでの極限は証明可能なものと証明不可能なものの間だけではなく、形式体系で捉えられるものと数学的実践を人間の活動として維持するもの(理解、洞察、進捗の感覚)の間にあります。自然言語が形式構文に還元されないように、生きた数学はその形式化に還元されません。