『ゲーデルの方法:決定不能な世界への探究』グレゴリー・チャイティン、ニュートン・ダ・コスタ、フランシスコ・アントニオ・ドリア 2011年

不確実性、不確定性、ランダム性物理・数学・哲学

サイトのご利用には利用規約への同意が必要です

『Gödel’s Way: Exploits into an undecidable world』要約


タイトル

英語タイトル:『Gödel’s Way: Exploits into an undecidable world』Gregory Chaitin, Newton da Costa, Francisco Antonio Doria 2011

日本語タイトル:『ゲーデルの方法:決定不能な世界への探究』グレゴリー・チャイティン、ニュートン・ダ・コスタ、フランシスコ・アントニオ・ドリア 2011年


目次

  • 第1章 ゲーデル、チューリング / Gödel, Turing
  • 第2章 複雑性、ランダム性 / Complexity, Randomness
  • 第3章 問題のリスト / A List of Problems
  • 第4章 停止関数とそのアバター / The Halting Function and its Avatars
  • 第5章 エントロピー、P vs. NP / Entropy, P vs. NP
  • 第6章 未踏の領域への遠征 / Forays into Uncharted Landscapes

本書の概要

短い解説:

本書は、ゲーデルの不完全性定理が数学の遠い領域に留まらず、物理学・経済学・生態学・計算機科学など科学の実践に直接影響を及ぼすことを論証する。チャイティンのオメガ数とダ・コスタ=ドリアの結果を結びつけ、決定不能性と不完全性が数学の至る所に存在するという主張を展開する。

著者について:

グレゴリー・チャイティン(1947-)はアルゼンチン系アメリカ人の数学者・計算機科学者。ゲーデル=チャイティン不完全性定理を証明し、純粋数学における「神のサイコロ」を示すオメガ数を発見した。ニュートン・ダ・コスタ(1929-)はブラジルの論理学者で、矛盾を許容するパラコンシステント論理の創始者。フランシスコ・アントニオ・ドリア(1945-)はブラジルの物理学者で、カオス理論の決定不能性を含む多数の不完全性定理を証明した。

テーマ解説:

  1. 決定不能性と不完全性の遍在性:ゲーデルとチューリングの発見は数学の特殊な領域に限定されず、あらゆる数学的・科学的領域に浸透している。

  2. アルゴリズム的情報理論:プログラムサイズによる複雑性の定義を通じて、数学的真理の本質に新たな光を当てる。

  3. 科学における実践的帰結:カオス、経済学、計算複雑性理論における決定不能性が現実の問題に影響を与える。

キーワード解説:

  • 不完全性定理:十分に強い形式的体系は、その中で真であるにもかかわらず証明も反証もできない文を含む。
  • 停止問題:任意のチューリング機械が与えられた入力で停止するか否かを決定する一般的なアルゴリズムは存在しない。
  • オメガ数(Ω):ランダムに生成されたプログラムが停止する確率。そのビット列はアルゴリズム的に既約であり、いかなる形式的体系もその大部分を決定できない。
  • アルゴリズム的情報量:ある対象を生成する最小のプログラムのビット数。情報内容の厳密な数学的定義。
  • パラコンシステント論理:矛盾を許容するが、それによってあらゆる命題が導出されるわけではない論理体系。
  • P vs. NP問題:多項式時間で解ける問題と、解の検証は多項式時間だが発見は困難な問題のクラスが等しいか否かの未解決問題。

要点要約

本書『Gödel’s Way』は、ゲーデルの不完全性定理を出発点として、決定不能性と不完全性が数学のあらゆる領域に遍在することを論証する。著者たちは、この現象が純粋数学の遠い領域に限定されず、物理学・経済学・生態学・計算機科学など科学の実践に直接影響を及ぼすことを示す。チャイティンのアルゴリズム的情報理論とオメガ数、ダ・コスタとドリアによるカオス理論・古典力学・ゲーム理論における決定不能性の証明を統合し、数学的真理の本質と科学的知識の限界に新たな光を当てる。

第1章ではゲーデルの生涯と不完全性定理の基本的な枠組みを解説し、チューリング機械と停止問題を導入する。ゲーデルの第一定理は「この文は証明できない」という自己言及的文を用いて、任意の十分に強い形式的体系が決定不能な文を含むことを示す。第二定理は、そのような体系が自身の無矛盾性を証明できないことを示す。チューリングは停止問題の決定不能性を示し、不完全性と決定不能性の深い関係を明らかにした。

第2章ではチャイティンのアルゴリズム的情報理論を展開する。プログラムの最小サイズとして情報量を定義し、オメガ数Ωを導入する。Ωはランダムなプログラムが停止する確率であり、そのビット列はアルゴリズム的に既約で、いかなる形式的体系もその大部分を決定できない。この結果はライプニッツの「充足理由の原理」に挑戦し、数学の中にも偶然性が存在することを示す。

第3章はダ・コスタとドリアの研究プログラムの紹介である。パラコンシステント論理の解説から始まり、一般相対論、カオス理論、経済学、P vs. NP問題、超計算理論にわたる未解決問題のリストを提示する。これらの問題はすべて決定不能性と不完全性の観点から再考されるべきであると論じる。

第4章ではカオスの決定不能性を中心に扱う。ダ・コスタとドリアはリチャードソンの結果を用いて、任意の力学的体系がカオス的か否かを判定する一般的なアルゴリズムが存在しないことを証明する。さらに停止関数の明示的表現を与え、それがオメガ数と密接に関連することを示す。この結果は経済学におけるナッシュ均衡の決定不能性や競争市場の均衡価格の非計算可能性へと拡張される。

第5章では情報理論のエントロピーとP vs. NP問題を扱う。シャノンの符号化定理の数学的構造を解説し、異なる集合論的モデルにおいてエントロピーがどのように振る舞うかを考察する。P vs. NP問題については、ダ・コスタとドリアの条件付き独立性証明を紹介する。P < NPが真ならば反例関数は全ての帰納的関数よりも急成長し、その結果P < NPはZF集合論では証明できない可能性が高いと論じる。

第6章は最も投機的な章であり、情報に基づく世界観、超計算理論、エキゾチックな時空構造を探求する。デジタル哲学の観点から「神はプログラマーである」というネオ・ピタゴラス主義を提示し、理想的なアナログ計算機による超計算の可能性を議論する。また4次元多様体のエキゾチックな微分構造が物理学に及ぼす含意と、時間の本質に関する哲学的考察で締めくくられる。


各章の要約

第1章 ゲーデル、チューリング

ゲーデルの生涯と業績を紹介し、不完全性定理の基本を解説する。ゲーデルは1906年ブルノ生まれ、ウィーン大学で学び、1931年に不完全性定理を発表した。第一定理は「この文は証明できない」という自己言及的文を用いて、任意の十分に強い形式的体系が決定不能な文を含むことを示す。第二定理はその体系が自身の無矛盾性を証明できないことを示す。クリーンによる別証明では、証明可能な全域関数のリストから対角化によって新しい全域関数を構成し、それが証明できないことを示す。

チューリング機械と停止問題の解説では、任意のプログラムが停止するか否かを判定する一般的なアルゴリズムが存在しないことを証明する。この結果はポストの議論を通じて不完全性と直結する。ヒルベルトの第10問題(ディオファントス方程式の解の有無を判定する一般的アルゴリズムの存在)の否定的解決も紹介され、計算理論と数論の深い関係が示される。

ゲーデルの宇宙論的解決(一般相対論における時間機械を持つ解)と、そのような解が典型的であるという確率的議論も含まれる。第2章ではこの決定不能性のより極端な形態としてアルゴリズム的ランダム性を探求する。

第2章 複雑性、ランダム性

アルゴリズム的情報理論の基礎を展開する。ワイルとライプニッツの複雑性概念から出発し、科学的理論を「実験データを生成する最小プログラム」としてモデル化する。エレガントなプログラム(その出力を生成する最小のプログラム)は無限に存在するが、いかなる形式的理論も有限個のエレガント性しか証明できないことを示す。

オメガ数Ωはランダムなプログラムが停止する確率であり、そのビット列はアルゴリズム的に既約である。すなわち、Nビットの理論は高々NビットのΩしか決定できない。この結果はライプニッツの「充足理由の原理」に反する——Ωのビットは何らかの理由があるからではなく、単にそうであるという偶然の事実である。

Ωのランダム性はディオファントス方程式や半群の語問題など、純粋数学の様々な領域に現れることを示す。最後に「メタボロジー」——生物学的進化の数学的モデルとしてソフトウェアのランダム進化を研究する新分野——の構想を提示する。第3章ではこれらの抽象的結果を具体的な科学問題へ応用する。

第3章 問題のリスト

ダ・コスタとドリアの研究プログラムを紹介する。まずダ・コスタのパラコンシステント論理を解説する。これは矛盾を許容するが、古典論理のように矛盾からあらゆる命題が導出されるわけではない論理体系である。この論理は科学的理論における矛盾を扱うための強力な道具となる。

続いて以下の問題群を列挙する:(1) 一般相対論におけるコーエンのフォーシングの応用、(2) カオス系の決定問題、(3) 平衡点の安定性の決定可能性、(4) 経済学における不完全性の影響、(5) シャノン定理と異なる集合論的モデル、(6) P vs. NP問題、(7) チューリング障壁の突破(超計算)。

特に一般相対論では、フォーシングによって「ジェネリックな時空」を構成でき、それが物理的に意味を持つ可能性を論じる。またシャノンの情報理論では、集合論的モデルの変更によってエントロピーが変化する現象を示唆する。第4章ではこのリストの中心的問題であるカオスの決定不能性を詳細に扱う。

第4章 停止関数とそのアバター

カオスの決定不能性を中心に扱う。ローレンツ系から始まるカオス理論において、ある力学的体系がカオス的か否かを判定する一般的アルゴリズムが存在しないことを証明する。この結果はリチャードソンの決定不能性定理を応用し、停止関数の明示的表現を構成することで得られる。

停止関数θ(n,q)は、チューリング機械nが入力qで停止するか否かを示す関数であり、解析学の言語で明示的に書けるが計算不可能である。この関数を用いて、任意の非自明な性質Pについて「xがPを満たす」が決定不能となるライスの定理の解析版を導出する。

この結果は経済学に直接応用される。アラン・ルイスとマルセロ・ツジは、ナッシュ均衡の決定不能性と競争市場の均衡価格の非計算可能性を示した。またロトカ=ヴォルテラ方程式を用いた生態学モデルや歴史予測の問題にも拡張される。最後に停止関数θとオメガ数Ωの関係を論じ、両者が本質的に同じ現象——停止問題——を表現していることを示す。第5章ではこの枠組みをP vs. NP問題へ拡張する。

第5章 エントロピー、P vs. NP

まずシャノンの情報理論におけるエントロピーと符号化定理の数学的構造を解説する。シャノン=マクミラン=ブライマン定理と等分配性を用いて、弱い雑音のある通信路で容量に近い速度で情報を伝送できることを示す。続いて、無限のコイントスゲームにおいて、計算可能な列を除去してもエントロピーが変化しないという結果を示し、エントロピーの「所在」に関する集合論的問題を提起する。

P vs. NP問題については、ダ・コスタとドリアの条件付き独立性証明を詳細に解説する。P < NPが真ならば反例関数f(n)(多項式機械nが最初に失敗する入力のコード)は全ての全域帰納的関数よりも急成長する。この性質により、ZF集合論を含むいかなる「合理的な」形式的体系もP < NPを証明できない可能性が高い。

さらにP = NPが真ならば、それはΠ₁文として表現でき、その場合ペアノ算術(またはそれに近い理論)が証明できることを示す。したがってP = NPとP < NPの両方が独立ならば、標準整数においてはP < NPが真である。この議論は反例関数の成長率と形式的体系の証明能力の関係に基づいている。第6章では超計算と時空構造というより投機的な領域へと踏み込む。

第6章 未踏の領域への遠征

最も投機的な章であり、情報に基づく世界観(デジタル哲学)を提示する。現代物理学の困難(量子場理論と一般相対論の矛盾、連続体の問題)に応えて、伝統的なピタゴラス主義(「神は数学者である」)をネオ・ピタゴラス主義(「神はプログラマーである」)へと更新することを提案する。

超計算理論では、理想的なアナログ計算機が停止問題を解決できる可能性を議論する。スカルペリーニの1963年の観察に基づき、ダ・コスタとドリアは停止関数の明示的表現を用いた超計算機のプロトタイプを構想する。この機械は真の算術(完全な算術理論)のすべての文を決定できる可能性を持つ。

4次元多様体のエキゾチックな微分構造と物理学への含意を探求する。ミルナー、ドナルドソン、フリードマン、トーブスの結果により、4次元ユークリッド空間は非可算無限の非等価な微分構造を持つことが知られている。これは時空がエキゾチックな構造を持つ典型性を示唆し、そのような構造では大域的「宇宙時間」が存在しない。

時間の本質に関する哲学的考察では、光速一定が時間の存在を導くという主張、ハイゼンベルクの第四不確定性関係(エネルギーと時間)、ファインマン経路積分による多宇宙解釈などを議論する。ユングの集合的無意識とパウリの関係に触れつつ、「これは夢が作られる素材である」という引用で締めくくられる。


想定読者・前提知識・読みどころ

  • 想定読者:数学・論理学・物理学・計算機科学・科学哲学に興味を持つ読者。専門家から教養のある一般読者まで幅広く対象とするが、特に基礎的な数学的思考に親しんでいる読者を想定。
  • 前提知識:高校数学程度の基礎知識があれば第1章・第2章の大部分は理解可能。第3章以降のより技術的な議論(特に第4章の停止関数や第5章のP vs. NP問題)には、大学初年級レベルの数学(集合論の基礎、計算理論の初歩)が望ましい。各章の冒頭で必要な背景が簡潔に説明されている。
  • 分量・難易度:約160ページの中程度の分量。専門用語が多いが、著者たちは「読みやすさのために厳密性を犠牲にすることを躊躇しない」と述べており、技術的な詳細よりも概念の理解に重点が置かれている。ただし第2章のアルゴリズム的情報理論と第5章のP vs. NP問題の議論は比較的高度。
  • 読みどころ:本書の核心は第2章(アルゴリズム的情報理論とΩ)と第4章(カオスの決定不能性とその応用)にある。第1章は基礎的概念の導入、第3章は研究プログラムの全体像を示す「地図」として機能する。純粋数学の哲学的含意に興味があれば第2章と第6章前半、応用面に興味があれば第4章と第5章を重点的に読むとよい。第6章後半は著者たち自身が「投機的」と認める内容であり、その点を念頭に置いて読むべきである。

 

理由なき真理 — 決定不可能性が遍在する世界 Truths True for No Reason: On the Ubiquity of Undecidability

理由なき真理:数学はなぜ自分自身を語りきれないのか

by Claude Opus 4.8

数学が証明する、自分自身の限界

最初に引っかかったのは、結論部の高揚だった。決定不可能性と不完全性があらゆる場所にある——この主張そのものには異論がない。むしろ厳密に正しい。引っかかったのは、その厳密な結果を土台にして「世界はソフトウェアである」「神はプログラマである」という形而上学が組み上げられていく、その手つきのほうだ。本書『ゲーデルの道:決定不可能な世界への探検』(Gödel’s Way: Exploits into an Undecidable World, 2011)は、チャイティン(Gregory Chaitin)、ダ・コスタ(Newton da Costa)、ドリア(Francisco Antonio Doria)という三人の数学者・論理学者・物理学者が、リオの屋外バーでの議論から生み出した本だという。

奇妙なねじれがある。この本の中核にある定理は、要するに「形式的・機械的な手続きですべての真理を汲み尽くす夢は不可能だ」と告げている。にもかかわらず、本は最後に「すべては計算である」と宣言して閉じる。完全性の夢を解体した同じ著者が、別の貌をした機械論を再建しているように見える。この違和感を、まず手放さずに進めたい。

ゲーデルからΩへ:不完全性の正体

順を追う。1931年、ゲーデル(Kurt Gödel)は「この文は証明できない」という自己言及で不完全性を見つけた。1936年、チューリング(Alan Turing)はそれが、より深い現象——計算不可能性——の系であることを示した。証明できないことの根は、計算できないことにある。そしてチャイティンは、計算不可能性のさらに極端な形、「アルゴリズム的既約性」へと降りていく。

その底にあるのが停止確率「Ω」だ。ランダムにビットを並べたプログラムが停止する確率を、一つの実数に畳み込んだもの。この数のビット列は、それ自身より単純な理由からは導けない。N桁を確定するにはN桁ぶんの公理がいる。証明とは本来「より少ないものからより多くを導く」操作だが、Ωのビットにはその圧縮が一切効かない。すべての冗長性を絞り尽くした結果として、完全に偶然に見えながら、実は停止問題の全解答を最も緻密に詰め込んだ数——それがΩである。

ここでチャイティンは美しい等式を置く。「説明とは圧縮である」。科学理論とは、データを出力する最小のプログラムのことだ。理論がデータと同じ大きさなら、それはもはや理論ではない。理解とは圧縮にほかならない。

ワイル(Hermann Weyl)を経てライプニッツ(Leibniz)に遡るこの発想は、深い帰結を持つ。ライプニッツの「充足理由律」——真であるものはすべて理由があって真である——を、Ωは正面から裏切る。Ωのビットは理由なく真なのだ。より正確には、それ自身より単純な理由を持たない。数学の底に、構造もパターンも理論もない一点が口を開けている。チャイティンが「純粋数学のなかで神がサイコロを振る場所」と呼ぶのは、ここだ。

「理性への別れ」ではなく理性の地図

立ち止まる。「理由なく真」とは、何を意味するのか。

ニヒリズムではない。これは特定の形式系に対して相対的な事実だ。ある公理系の射程の外に、その系では決して決着できない命題が無数にある——それだけのことだ。だが「それだけ」が深い。単一の真理へすべてが収束するという像が、ここで原理的に崩れる。

チャイティンはこの状況への処方箋を、物理学から借りてくる。不完全性に出会ったら、新しい公理を足せばよい。自明だからではなく、有用だから足す。マクスウェル方程式やシュレーディンガー方程式が自明でないのと同じ意味で、それでも機能するから採る。彼はこれを「準経験的数学」と呼ぶ。この語はラカトシュ(Imre Lakatos)に由来し、章の見出しに彼が借りた「理性への別れ」はファイヤアーベント(Paul Feyerabend)の書名(Farewell to Reason, 1987)だ。

ここで私の警戒は、共感に近づく。数学を、自明な公理から演繹される伽藍ではなく、共同体が道具を交渉しながら更新していく実践として見る——この眼差しは正しい。証明はデカルト的な確実性の連鎖ではなく、伝統に埋め込まれた営みなのだ。完璧な公理が上から降りてくるのではなく、下から、実践の必要に応じて立ち上がる。認識が「自明性」という硬直から解き放たれる。複数の整合的な公理体系が並び立ち、どれを採るかが選択の問題になる——これは認識の多元性そのものである。

予測できない未来:形式の傲慢が砕けるところ

そして決定不可能性は、純粋数学を出てゆく。ここが本書の野心の核心だ。

ダ・コスタとドリアは、カオスが決定不可能であることを証明した。力学系が安定か不安定かを判定する一般的アルゴリズムは存在しない。古典力学そのものが不完全になる。これは計算機科学のライスの定理を、解析学(微積分)へ映し返した結果だという。さらに経済学へ。ルイス(Alain Lewis)とツジ(Marcelo Tsuji)は、ナッシュ均衡が——再帰的に記述できるゲームであってさえ——計算不可能でありうることを示した。ヴェルピライ(Vela Velupillai)はさらに踏み込む。経済主体の合理性をチューリング機械と同一視するなら、その選好順序は決定不可能になる、と。

「歴史的事象の未来を予測できるか」。著者たちの答えは端的だ。否。

ここには、形式化への信仰に対する静かな批判が埋まっている。数理経済学が誇る一般均衡理論は、厳密な意味で計算可能でも構成可能でもない。ヴェルピライの論文題はずばり「経済学における数学の理不尽な無効性」(The unreasonable ineffectiveness of mathematics in economics, 2005)。形式化は、ある閾値を超えると、理解を増やすどころか、自らの予測能力が原理的に届かない領域を露わにする。道具が精緻になるほど、その道具では触れられないものの輪郭が際立つ。これは医療や統計的エビデンスの過信にもそのまま響く話だ。完璧な大規模試験を待つことと、目の前の判断を下すことは、別の時間に属している。「証拠がないこと」と「効果がないこと」を取り違える誘惑は、形式の射程を過信するところから生まれる。

老子とボレルの実数:名づけえぬものの海

では、私が抵抗した最後の跳躍——「世界はソフトウェアだ」——をどう扱うか。

ここで一つ思い出す。ボレル(Émile Borel)は、名づけることのできる実数が確率ゼロであると示した。名指せる数は、名指せない数の大海に浮かぶ測度ゼロの島にすぎない。計算可能な実数もまた、全体のなかでは確率ゼロだ。

老子の冒頭が重なる。「道の道とすべきは、常の道に非ず」。名づけられた道は、永遠の道ではない。形式化できるもの・名づけられるもの・計算できるものは、語りえぬものの海に浮かぶ小さな島だ。チャイティンの数学は、東洋の古い直観に、厳密な測度論的な裏づけを与えていると言ってよい。

だからこそ、「神はプログラマである」という結論は奇妙に映る。語りえぬものの遍在を証明した本が、最後に「すべては計算だ」と語る。これは真理の主張としては越権だ。数学が示したのは形式系の限界であって、宇宙が計算機であることではない。世界がソフトウェアでできているという命題は、数学が許す以上の何かを密輸している。デジタル哲学やホログラフィック原理を引きながらの神=プログラマ論は、ピタゴラス的「神は数学者」を別の語彙で言い換えただけの、新たな形而上学的賭けにすぎない。

ただし——ここが肝心だ——誤りであることは、無価値であることを意味しない。「世界はソフトウェアか」という問いは、真理の軸では行きすぎでも、生成の軸では豊かだ。多宇宙の測度問題が、宇宙=プログラムと見れば「2のマイナス|p|乗」できれいに解ける、というテグマーク(Max Tegmark)経由の議論は、答えとして正しいかどうかより、新しい探求を開く触媒として効いている。

「神はプログラマ」を真理の終着点として住み着くのではなく、探求を駆動する装置として持ち、必要なら手放す。著者たち自身、終盤の思弁を「これは夢から作られている。力強い夢だ」と結んでいる。彼らはそれが真理だとは言っていない。思弁的(speculative)だと明記している。読む側が結論を実体化しないかぎり、この本の越権は越権でなくなる。生成装置として使いこなせばよい。

総括

本書の恒久的な価値は、ライプニッツとヒルベルトが抱いた「全的理性」の夢——自明な公理からすべての真理を機械的に導けるという夢——が不可能であることを、完全な厳密さで証明した点にある。しかもその不可能性は、論理学の希薄な辺境に閉じた珍奇な現象ではなく、物理学・古典力学・経済学、そして歴史の予測可能性にまで届く、遍在する構造的事実だ。最も深い教訓は、数学的な裏づけを持った認識の謙抑である。形式化できるもの・名づけられるもの・計算できるものは、語りえぬものの大海に浮かぶ測度ゼロの島でしかない。

一方で、その島の外に広がる海を「これもまたソフトウェアの海だ」と命名し直す身振りは、真理の主張としては受け取らない。それは数学が証明した「限界」を、こっそり「全域」へ読み替える操作だからだ。生成装置として用い、真理として住み着かない——この距離が要る。

そして本書は一つの問いを開いたまま閉じる。理解が圧縮であり、世界の最も深い事実が圧縮不可能だとすれば、Ωが画する限界は「理性そのもの」の限界なのか、それとも「計算という一つの理性像」の限界にすぎないのか。圧縮できないものは理解できない、と言い切れるのか。それとも、圧縮とは別の様式の理解がありうるのか。この問いは決着しない。決着しないことを正直に引き受ける場所が、この本を読み終えたあとに残る、最も誠実な立ち位置である。

タイトルとURLをコピーしました