高橋昌一郎 「ゲーデルの哲学」

読書




以前読んだゲーデル 不完全性定理はけっこう専門的に書かれていて難解だったのに対し、本書は平易に書かれており、数学的な正確さよりもゲーデルの不完全性定理の雰囲気をわかりやすく説明することを重要視していたので比較的読みやすく楽しく読めた。


最終章にこれまで詳細がよく分からなかったチャイティンの定理がわかりやすく説明されていた。
定理は以下のようなもの。

「任意のシステムSにおいて、そのランダム性を証明不可能なランダム数GがSに存在する。」

証明：

  • システムSの公理と推論規則を記述するプログラムを二進法にコード化したプログラムをnビットとする。
  • Sは自然数論を含むのでその内部で任意の自然数を表現できる。
  • もしSがnビットよりも長い数列のランダム性を証明できるならば、S内部にはそのランダム性を証明可能にするnビット以内のサブプログラムが存在することになる。
  • しかし、ランダム性の定義(ランダムな数列はそれ自体よりも圧縮できない)により、nビットよりも長いランダム数はそれよりも圧縮されたプログラムでは表現不可能である。
  • これは矛盾であるのでSはnビットよりも長い二進法にコード化される自然数のランダム性を証明できない。

もうちょっと続きがあって最終的には「真理性Ωはランダムである。」ということらしいが、この辺はよく分からず。。

要するに、任意のシステムSにはS内部ではそのランダム性を証明不可能なランダム数Gが存在するので仮に神が存在するとしても人間には認識できないということかなと思う。この辺りは苫米地理論とも一致するように思う。