不完全性定理から証明された「真理性 Ω は、ランダムである」とはどういうことですか？

質問

ゲーデルの不完全性定理の応用でチャイティンが、
「任意のシステム Ｓ において、そのランダム性を証明不可能なランダム数Ｇ が存在する」
という事を証明し、その後「真理性 Ω は、ランダムである。」という定理を発表したようですが、

この「真理性 Ω は、ランダムである。」とはどういう意味なのですか？
論理学も数学もほとんど無知ですが感覚的に分かるように説明して頂けませんか。よろしくお願いします。

回答No.1

tshmsg63 · ベストアンサー

チャイティン氏の理論は「アルゴリズム的情報理論」と呼ばれ、外見上は「コンピュータ・プログラム理論」の体裁ですが、その数学的帰結はいわゆる「証明論」や「超数学」等の数学の根本を扱う分野にそのまま適用することができるとされています。

Ωの定義を普通の言葉で言い直せば、「ある公理系内で無作為に一つの命題を選び出したとき、その命題がその公理系内で決定（証明又は反証）可能である確率」であり、またチャイティン氏の言う「ランダム」とは「計算不可能」、広義には「その命題なり数なりを導出する方法が一切存在しない」ということと同義のようです。

従って、「真理性Ωはランダムである」を言い直せば、

「ある公理系内で無作為に一つの命題を選び出したとき、その命題がその公理系内で決定可能である確率は、（実際には決まっているはずなのに）一切いかなる方法によっても導出することが出来ない」

ということになるかと思います。さらに具体的に言うと、

「Ωを２進数で表したとき、小数点以下のある特定の範囲以降の各桁が１であるのか０であるのかを、計算によって決定することは不可能である」

ということです。（ちなみに、その各桁が何であるかを決める数学的根拠を提示することが不可能であるということから、この各桁の並び方をコイン投げの裏表の出方に例え、そのことをもランダムと言う言葉で表しています。）

このように言うとさほど大きな重要性が感じられないかもしれませんが、「Ωがランダム（計算不可能）である」という事のインパクトは実際にはもっと大きく、そこから導かれる帰結にさらに大きな意義があると考えているようです。そのような重要な帰結の一つが、ゲーデルのG命題よりもさらに重要な「絶対的に決定不可能な命題」の提示であり、そのような命題にかかわる方程式を彼は実際に論文で書き下しているようです。

詳しくは（もしまだお読みでなければ）チャイティン氏の著作、「セクシーな数学」や「メタマス！」がお勧めです。アマゾンや楽天でいつでも入手できると思います。

お礼

回答ありがとうございます。ネットで検索しても詳しく説明したところがなく、困ってました。
ぱぱっと読んだだけじゃ理解できなかったのでこれからじっくり読んで理解してみます。

チャイティンの本に関してはあったことすら知りませんでした。読んで見たいと思います。

本当にありがとうございました。