あなたにも(たぶん)わかる
「ゲーデルの不完全性定理」
-- 発端<ほったん>編 --

檜山正幸 (HIYAMA Masayuki)
Mon Dec 26 2005:start
Wed Dec 28 2005:draft
Tue Jan 03 2006:prefinal

僕は、ゲーデルの(第一)不完全性定理の初等的な解説をしようと思う(こ の記事でするわけではない)。その動機とか方針とかを述べておく。

目次

1. ゲーデルの定理は神秘主義の対極にある

ゲーデルの不完全性定理を、自然言語(日常言語)だけで説明する試みを見 かけるのだけど、これは無理スジじゃなかろうか。前もってわかっている人は、 「あー、そうだね、確かに」と納得できるだろうが、その自然言語による説明 により初めて勉強をする(そして、ちゃんと理解する)ってのはほぼ不可能な 気がする。

一見回り道のようでも、記号論理学を一通り勉強して、ゲーデル符号化を (だいたいでも)追いかけないと、納得した気分にはなれないだろう。仮に正 確な説明だったとしても(そうじゃない例も見かける)、それが自然言語で記 述されると、なんだか騙されたような印象をぬぐいきれない。

ゲーデルの定理を哲学的に解説するのはやめたほうがいいと思う。いやっ、 たしかに哲学的に重大な意義を持つだろうし、ゲーデル本人も背景になんらか の哲学(指導原理)を持っていたかもしれない -- それは認める。だけど、ゲー デルがすごいのは、記号論理のノーマルな記述と手法だけで、 哲学的/宗教的(?)議論に一切たよらず、なんら神秘的なことをせずに、信じ がたいような結果をキッチリ出したところだ。

曖昧模糊とした自然言語の表現で、信じがたいようなことを言ってみるのは 簡単だ。きちんと形式化されてない言明は、それがウソかマコトか検証できな いから、まー、なんとでも言えるさ。ゲーデルは、検証可能(したがって反駁も可 能)な、徹底的に明白な形式/表現で不完全性定理を述べているわけで、神秘 的な神託をたれているわけじゃない。

ところで、「ゲーデルの不完全性定理」のゲーデルによる記述はすべてが明晰だが、 ゲーデル自身はひょっとしたら神秘主義的傾向があったのかもしれない(あて ずっぽう!)。明白、明晰を追求すれば必然的に限界に出会うという事実を前 にして、それでも絶対的な真実があると信じたいならば(あくまで仮定)、人 知を超越した存在を認める気分になるかもしれない(まったく、あてずっぽう!)。

2. 「あきれるくらいの明晰さ」としてのゲーデルの定理

最近僕は、“検証可能(したがって反駁も可能)なほどに明白”な記述や言 明に興味を持っている。その背景には、トンデモな言説が社会的な影響を持っ たりする異常な(と僕には思える)事態がある(*注1)

注1

例えば、僕の日記エントリー“VOODOOな理論達:「水は生きている」騒動、そしてそれから”を参照。 関連するエントリー群は、“ブックマーク「VOODOO」”にまとめてある。

それと、たまたま、形式的論理体系に関する説明 (をする日記エントリー)(*注2)を書いたりしたので、ゲーデルが気になりだし た。気分としては、「一般教養としてゲーデルの不完全性定理は知っておけよ」 なんだが、さすがにこれは言い過ぎ! そう、言い過ぎなんだけど、ものごと を徹底的に考え抜き、徹底的に明白に記述する、という例として、ゲーデルは もの凄く魅力的だ。

注2
例えば、“極大 (無矛盾)セオリー”。あと、 “論理に関するメモ”とか。

ゲーデルがやったことは、二重の意味で猛烈に論理的なのだ。この「論理的」っ てのは、この何年か多少流行っている「論理的」(ロジカル・シンキングとか なんとか、そんなやつ)とはもうレベルが全然違う、ホンモノの論理的だ!

まず、ゲーデルが研究した対象が“形式化された論理体系”。つまり、ゲー デルは論理について考えたことになる。そして、その考察や分析の行為 が極めて論理的。だから、“論理について論理的に分析した”と言える。分 析の対象である論理体系と、分析者(自分)が分析行為に使う論理を混同しが ちなんだが、ゲーデルはイヤになるくらい明晰に区別している。

ゲーデルの発想/アイディアはもちろんすごいのだけど、記号論理や形式的 算術に関する技量・腕力もハンパじゃない。確か、前原昭二先生がどこかに書 いていたと思うのだが(記憶は曖昧、出典不明)、ゲーデルが技術的腕力で乗 り越えた部分(ゲーデル符号化やメタ言明の算術化など)をスキップして哲学 的解釈にふけっても不毛だろう。(うーん、ほんとに前原先生がそう言ってい たのか? 自信なくなった。)いくら素晴らしい発想があっても、あの腕力が なかったら、不完全性定理は“定理”になっていなかった。不完全性定理 に相当することを実質的に認識していた人は、ゲーデル以前にもいただ ろうが、ゲーデルほどに明晰に記述することができなかったのだ。

3. 「一般教養としてゲーデルの不完全性定理」の可能性

さて、「一般教養としてゲーデルの不完全性定理」を学ぶってのは、ほんと に無理なのだろうか。冒頭にも書いたように、僕は、自然言語による説明には まったく期待を持っていない。かといって、正統的に記号論理から解説するの も手間がかかり過ぎる。抜け道はあるか? …… あるかもよ。あるような気が している。

計算の理論において、「停止問題の決定不可能性」はよく知られている。これを 示すには色々な方法があるが、嘘つきのパラドックスを利用することにする。 つまり、停止性判定プログラムがあると仮定して、命題「私は停止しない」を 意味するプログラムを作る。

「私は停止しない」プログラムが停止して命題が真ならば、私(そのプロ グラム)は停止しない。一方、「私は停止しない」プログラムが停止しない なら命題が真ではない(停止しないなら真と断定はできない)から、メタ判断 を二値的にする(停止しないは偽と解釈する)なら、“私は停止しない”でな いから、私は停止する

あー、なんだか冒頭で触れた「自然言語で記述されると、なんだか騙された ような印象をぬぐいきれない」つう説明を自分でやっている、ウギャー。それ でも、いちおうまとめてみれば:

わかる?無理かなぁ。無理だろな(*注3)。まー、それでも、停止しないプログラム の存在は、プログラマの生活実感から受け入れることができるよね。そし て、ゲーデルの不完全性定理のプログラミング的解釈は、真偽判定を行うプロ グラムが仮に出来たとしても期待通りには動作せず、ときに無限走行してしま うってこと。無限走行の可能性を認めない限り、嘘つきパラドックスの呪いで 議論は破綻する、それはあり得ない。ところが、実際に無限走行するなら、そ れは真偽判定プログラムとは呼べない。つまり、真偽判定プログラムなんて出 来ないのだ。

注3

2006-01-05に分かりやすくなるように工夫して書き換えた。でもやっぱ り、なんだかワケワカランだと思う。

不完全性定理の別な側面として、仕様が曖昧性無くキッチリ決められていて も、実装できない(プログラムが実際には書けない)ことがあるって指摘が含 まれる。真偽判定をするプログラムは、仕様は書けてもプログラムは書けない 例。(「実装できないプログラム」って言い方はそもそもおかしいかも、 “プログラムとして書けないプログラム”のことだからね。)

ともかくも、説明の基本的方針としては、停止しないプログラムって概念を 利用する。あと、ゲーデル符号化はコンパイルと解釈して、 帰納的に枚挙可能な定理集合は、無限に定理をはき出し続けるプロセスと解釈 する。こうして、プログラマにお馴染みの概念だけでゲーデルの不完全性定理 を解説できる気がするのだ。

4. 参考文献など

レイモンド・スマリヤン著(高橋昌一郎訳)『ゲーデルの不完全性定理』 (丸善, 1996)は、不完全性定理をテーマにした入門書(程度が低いわけでは ない)だ。著者のスマリヤンは、教科書でも読み物でも面白いものを書くので 定評がある。が、訳文・訳語はどうもいただけない、もう少し読みやすい日本 語にして欲しかった。僕はこの本を持っているが実はあまり読んでない。

ゲーデルの原論文(の英訳)が載っている本として、"From Frege to Godel" が有名だが、僕は実物を見たこともない。あまり知られてないようだが、 Doverから論文英訳に解説を付けた薄い本"On Formally Undecidable Propositions of Principia Mathematica and Related Systems"が出ている。 5ドル95セント(購入当時)、お買い得。

ゲーデルの原論文のていねいな解説を前原昭二先生がしていて、僕が読んこ とがあるのは、この解説だけだ。おそらく、前原昭二著『数理論理学 : 数 学的理論の論理的構造』(培風館, 1973)だったと思うが、紛失して手元に ないので確信はない。ひょっとすると、朝倉書店から出ていた前原昭二著 『数学基礎論入門』(1977)かもしれない(これも手元にないし、そもそ も読んだかどうかも不明)。

そんなわけで、参照すべき(僕にとっての)原典は残っていない。前原先生 の2冊は入手したいのだが、本屋で(古本屋でも)見かけたことはな い。最近、辞書代わりに使っている 小野寛晰著『情報科学における論理』 (日本評論社, 1994)に不完全性定理の記述があるかと思ったら、それはなかっ た。しかし、コラムとして鋭いコメントがあって参考になる。それに触発され て書いた日記エ ントリーもある。

停止問題の決定不可能性をいつどこで知ったかは何も憶えてない。計算論と かの本にはたいてい書いてあるだろう。

・ アマゾンへのリンク