2016年04月27日

不完全性定理


竹内薫『不完全性定理とはなにか-ゲーデルとチューリングの考えたこと』を読む。

不完全性定理.jpg


本書は,「各章は,不完全性定理の歴史の順に」並んでいる。著者曰く,

「革命的な理論が『わからない』と感じたときは,…『歴史』を書いた本を読むと,目から鱗が落ちることがある。なぜなら,歴史的な視点で学問の発展を追うことにより,革命前夜の混乱と,革命後の整理整頓された知的状況が俯瞰できるから。」

と。で,ペアノ算術の公理から,多宇宙仮説までをフォローする。それは,著者の言う,

(理数系)3わからん,

つまり,

アインシュタインの相対性理論,
量子論(不確定性定理),
ゲーデルの不完全性定理,

をカバーしている。ゲーデルのしたことは,

「基本的には,数学におけるメタフィクションに他ならない。」

という通り,「数学の『外』に出て,…数学の全体像を眺める」ことである。たとえば,例の,

(嘘つきのクレタ人が)「クレタ人は嘘つきだ」と言った,

という文章について,

「意味論の範囲にとどまるかぎり,…循環は無限に続いてしまう。(中略)ゲーデルは,この嘘つきのパラドックスにヒントを得て,意味論から構文論へと舞台を変え,証明できることと真であることは別であることを示すために,『この命題は証明できません』ということを証明」

した。ゲーデルのメタ化は,こんな手続きである。

「「『この命題は証明できません』は証明できません」は証明できません」

という自己言及の無限後退を避けるために,

「ゲーデルの天才は,とんでもないことを思いついた。…『この命題』に数字の番号を付けて,(中略)『符号化』(coding)もしくは『コード化』(中略),ようするに,同じ機能をもった別の記号におきかえよう」

ということをした(ゲーデル数化)。この時点で,メタ・ポジションに立っている。

「この方法の素晴らしいところは,あらゆる命題だけでなく,あらゆる証明も背番号で呼ぶことができる点。なぜなら,証明というのは,…命題がずらずらと並んだもののことだから」

で,

「証明は必ず有限個の命題の集まりである。ところが,素数は無限個あるので,ゲーデル数に置き換えると,すべての命題,つまり過去に証明されたすべての命題から,これから未来永劫にわたって証明されるであろうすべての命題も,それぞれ固有のゲーデル数で表現することがかのうになるのである!」

そこで,著者は,不完全性定理の証明のあらすじを,次のように説明する(数式をカットした)。

ステップ1 1変数の命題F(y)を網羅した一覧表をつくる。Fの下添え数にゲーデル数をいれる
ステップ2 「Fk(l)」の形式証明のゲーデル数xが存在する」という命題を考える。数式略記する。
ステップ3 命題のkとlを変数yに置き換え,否定した命題を,数式化する。此の数式は,ステップ一の一覧表のどこかにあるはずである。それがn番目だったとする。
ステップ4 変数yに自分自身背番号,すなわちゲーデル数nを代入する。
ステップ5 ステップ4でつくった命題の右辺は,「Fn(n)の形式召命のゲーデル数が存在しない」となる。対応するゲーデル数が存在しないのだから,それは,Fn(n)が証明できない

と。Fn(n)=の右辺が証明できないという命題ができた,ということになる,というプロセスである。

「形式証明は規則的な式の変形に過ぎない。真理関数のような外部殿関係性は出てこない。それなのに,なぜ,『真だけれど証明できない命題』というような意味論的な説明がなされているのか?(中略)
 実は,ゲーデルの考察にペアノ算術が入ってくるため,このような混乱が起きてしまうのだ。たしかにゲーデルの証明は純粋の構文論の世界である。だが,『ペアノ算術を含むシステム』を考え,ゲーデル数の方法により,システム内の式のすべてを『数』に翻訳してしまう。そうなると,算術はすなわち数同士の関係にほかならないから,算数の式として,『真』であるにもかかわらず証明できない,という気持ち悪い状況が出現するのだ。(中略)そもそも『意味』とは,記号と記号外部との関係性にほかならない。で,ゲーデルの不完全性定理は,ゲーデル数によつて,システム内部に含まれる算術との関係性が生じるので,意味が『自然と湧き出てくる』…。自分自身について考えるシステム,すなわち超数学ならではの不可思議な現象だといえるだろう。」

チューリングは,決定問題を考えていく過程で,ゲーデルの不完全性定理と同じことを別の視点から証明することになる。

「決定問題とは,数学の個々の問題が真か偽かを決定する手順のことだ。たとえば命題論理は真偽表の方法が存在するから決定可能だ。でも(ふつうの)述語論理は決定可能ではない。」

チューリングは,公式や推論規則といった道具の代わりに「計算する機械」,「チューリング機械」を考えた。問題は,

「実用的な計算につきものの『計算は終るか』,あるいは『プログラムは停止するか』という,切実な問題だったのである。」

停止問題の証明のあらすじは,次のようなステップで説明される。

ステップ1 あらゆる計算にそれぞれ特化したチューリング機械Tに背番号(添え字)をつけて縦に並べる。
ステップ2 Tに入力できるデータ(1,2,3…)を横に並べる。
ステップ3 各チューリング機械に1,2,3…を入力した出力結果を一覧表化する。この表は,あらゆる可能なチューリング機械にあらゆる可能な値を入力した結果であり,機会が停止して具体的な数値を出力するか,停止せずに走り続けるかは決まっていると仮定。
ステップ4 出力の対角線をまるで囲んで,各出力を替えてしまう。たとえば,「1を足す」。この結果を与えるチューリング機械をDと呼ぶ。
ステップ5 ステップ4で作ったチューリング機械も,チューリング機械である以上,一覧表のどこかにあるはずだが,どこにも載っていない。
ステップ6 一覧表に載っていないということは,そもそもの過程,任意のチューリング機械が停止するかしないかは決められない。

コンピュータ科学者のG・チャイティン(「ゲーデルの証明は好きになれなかった」と言ったそうだ)は,ゲーデルとチューリングの差を,

「ゲーデルの場合は,公理系の内部構造,原始帰納定義スキーマ,および,かれの番号付が複雑なのでした。チューリングの場合は,彼の万能チューリングマシンのインタープリタープログラムが複雑でした。」

と,そのわかりにくさは,ブラックボックスの内部構造にある,ということらしい。いずれにしても,記号論理学になじみのないものにはわかりづらい。

さて,こうした数学上の「不完全性定理」は,物理学にどんな影響を与えたのか。

http://ppnetwork.seesaa.net/article/416793184.html

で触れた,ブライアン・グリーンは,マックス・テグマークの「数学宇宙仮説」を紹介している。それは,

「この宇宙は数学により記述される。宇宙のあらゆる物理法則は数字なのだ。」

ということになる。

「もしこの考えが正しいなら,この宇宙は単なる数学シミュレーションだ,という結論にならざるをえない。そして,数学シミュレーションであるならば,それが描き出す宇宙の姿はひとつとはかぎらない。数学シミュレーションはパラメーターや初期値や方程式を変えるだけで,別の宇宙を創りだすだろう。つまり,もし宇宙が数学シミュレーションにすぎないのであれば,宇宙は,われわれの宇宙だけであるはずがない。」

と,今日の多宇宙仮説へとつながっていく。

「そもそもゲーデルやチューリングが発見したことは,『システム内で~』という点が重要なのだ。個々の宇宙のシミュレーションが個々のプログラム,いいかえるとチューリング機械に相当するなら,すべての宇宙のシミュレーションは万能チューリング機械に相当するだろう。(中略)この宇宙全体をひとつのシステムとみなし,あらゆる物理現象の背後に『計算』が存在する,と仮定して,ゲーデルの定理やチューリングの定理を当てはめることも可能だろう。しかし,最近の物理学では多宇宙の存在がふつうに論じられている。それは厳密に形式的に論じられているわけではない。だから,この宇宙内では証明できない物理法則(?)があるとしても,それを別の宇宙から見ている観測者がその物理法則を『あの宇宙ではこんな物理法則が成り立っている』と証明することは可能だろう。」

結局,視点というか,同じことだが,立ち位置の問題に行きつく。

「相対性理論と量子力学(不確定性原理)と不完全性定理に共通するわからなさは,『視点を意識しないといけない』ということなのだと思う。相対性理論では,『誰が何を観測しているのか』,(中略)量子力学についても,観測装置の向きによって,観測される数値が変ってしまうのだ。(中略)ゲーデルの俯瞰是正定理も,メタな視点から数学を考察する以上,誰が何を計算(証明)しているのかが決定的に重要になってくる。」

と,著者が最後に指摘することは印象深い。更に敷衍すれば,視点は,

誰が,

という主体によって,

そのパースペクティブ,

が決定づけられる,それを決するのは,あえて言えば,

位置が,どこか,

が鍵になる。このことは,敷衍できる,ものの見方の鍵になりそうである。

参考文献;
竹内薫『不完全性定理とはなにか-ゲーデルとチューリングの考えたこと 』(ブルーバックス)



ホームページ;
http://www.d1.dion.ne.jp/~ppnet/index.htm

今日のアイデア;
http://www.d1.dion.ne.jp/~ppnet/idea00.htm

posted by Toshi at 05:04| Comment(0) | 書評 | 更新情報をチェックする
この記事へのコメント
コメントを書く
コチラをクリックしてください