＊書籍紹介と引用元とページ数などを追記しました。（１月６日）
久々に以前の講義を振り返ってみると、かなり面白いかと思います。
というのも、コンピュータサイエンスや、クリプキの様相論理学の完全性、ブラックホールの熱力学などを学び終わった視点で再びゲーデルを中心とする不完全性定理を見直すと、以前は見えなかったことが多く見えて楽しいでしょう（多分）。
簡単に言えば、ゲーデルが示したことを、チューリングがトレースし直して、チャイティンが完成させたのが、不完全性定理のざっくりとした歴史です。
チャイティンはこう語ります。
「手短に言うと、ゲーデルは不完全性を、チューリングは計算不可能性を、私はランダム性を発見しました。」（チャイティン 知の限界 p.3)
あまりに手短すぎますが、、、(；・∀・)
続けていわく
「私のアプローチは、ゲーデルやチューリングの方式同様に複雑ですが、その複雑さが異なります。ゲーデルの場合は、それは公理系の内部構造、原始帰納定義スキーマ、および、彼のゲーデル数の番号付けが複雑なのでした。チューリングの場合は、彼の1936年の論文で説明された、万能チューリングマシンのインタープリタープログラムが複雑でした。私の場合には、（チューリングの複雑な万能マシンに相当する）LISPインタープリターが複雑です。これはみなさんには見えません。」（同上 p.124)
議論の土台はゲーデル、チューリング、チャイティンで三者三様です。どれも複雑ですが、複雑さの見え方が異なるということです。
ゲーデルは公理系という土台で議論を展開し、チューリングはチューリングマシンという土台の上で議論を展開しました。公理系もチューリングマシンも無限を内包しますが、しかしアルゴリズムはシンプルであり、いま考えれば思考実験によるコンピュータです。
そしてチャイティンはLispというプログラミング言語を使いました。テクノロジーの進歩が数学に追いついたというべきでしょうか。
ゲーデルの公理系自体は歴史は古く、さかのぼればユークリッドの原論に至ります。ユークリッドの定義、公理と公準からスタートするシステムは初期値とアルゴリズム（関数）を入れて走らせるコンピュータと同じとみなせます。ユークリッド原論を純粋に形式化し、Syntax（統語論）だけで表そうとしたのがヒルベルトの野望です（ビールジョッキ思想に関しては何度かブログでも言及しました。拙記事「点と直線と平面というかわりに、テーブルとイスとビールジョッキと言ってもかまわない」）。それが完成したと思われたのが、ラッセルとホワイトヘッドのプリンキピア・マテマティカです。
そのプリンキピア・マテマティカを土台にして、ある公理系における決定不能命題について語ったのがゲーデルです。
それを翻訳しなおしたのがチューリングであり、公理の証明とは所詮は公理の計算にすぎないことに着目しました。証明も計算も機械的な作業です（これが機械的な作業だと感じるためには、プログラミングもそうですが、記号論理学の論理演算を少しやると良いと思います。長い定理の論理式を規則に従って計算していくと、最後に真理値が判断される状態になります）。証明が計算であるならば、計算は計算機の仕事です。そのために、チューリングは「計算が終わるかどうかを事前に知ることができるか」という問題に不完全性定理を読み替えたのが、偉業でした。
言うまでもありませんが、それを定数であるはずの停止確率Ωに切り替えたのがチャイティンです。
チャイティンの定数であるΩは定数なのに変数としてふるまいます（ざっくりすぎる議論ですが）。
今回はゲーデルにフォーカスしていますが、ゲーデルの手法は鮮やかです。
ゲーデルは、これまでぼんやりと「嘘つきのパラドックス」として知られていたパラドックスをきちんと形式化することに成功しました。この形式化、すなわち、数学でパラドックスを記述できたということがポイントです。その後、チューリング、チャイティンがまた別な形でより洗練させていきます。そのことで自然数論から数学全体に拡張していくのです。
ゲーデルは不完全性定理を示した論文で、この「嘘つきのパラドックス」についても言及しています（ただし丁寧な脚注付きで）。
（引用開始）
以上の議論がリーシャルのパラドックスと類似していることが注目される。「うそつきのパラドックス」とも密接に関わっている。（脚注１４どんな認識論的パラドックスも、決定不能命題の存在論の同様な証明に使える）
（引用終了）(原典解題 ゲーデルに挑む 証明不可能なことの証明 田中一之著 東京大学出版会 p.33）
ポイントは「リーシャルのパラドックス」や「うそつきのパラドックス」ではなく、『どんな認識論的パラドックスも、決定不能命題の存在論の同様な証明に使える』というところでしょう。別にうそつきのパラドックスでなくても構わないのです。
うそつきのパラドックス自体がなぜパラドックスなのかを簡単に復習しておきましょう。
不完全性定理のネタとなるパラドックス（嘘つきのパラドックス）自体は新約聖書に（それとは意識せずに）書かれていますし、ラッセルのパラドックスに至るまでに様々な変奏曲があります。
このパラドックスは、シンプルに言えば「私は嘘つきだ」という命題です。この命題が真ならば、この「私」＝「嘘つき」となり、その言葉はすべて「ウソ」となります。ならば、すべての命題は偽となるので、排中律が成立するとして、「私は嘘つきではない」、すなわち「私は正直者だ」ということになります。すると、正直者が言う「私は嘘つきだ」という命題は真であり、私＝嘘つき、は正しいということになります。すなわち、私が「正直者」か「嘘つき」かは決定不能に陥ります。どちらかが真だとすると、逆の結果が出力され、偽だとするとまた逆の結果が出力されます。この論理演算は停止しません。
ちなみに誤解されがちですが、自己言及がいつもパラドックスを引き起こすわけではありません。
反例を１つあげれば十分なので、たとえば「私は正直者です」という自己言及命題はパラドックスを引き起こしません。真なら真ですし、偽なら偽です。自己言及する命題がパラドックスを起こすのではなく、自己言及する命題のうちパラドックスを起こす命題があるということです。
この意味論的なパラドックスをどう形式化するかは非常な困難があります。
集合論で行えばラッセルのパラドックスとなります（ちなみにプリンキピア・マテマティカの冒頭にフレーゲに対する質問としてこのパラドックスをラッセルが提示したことが書かれています）。
ゲーデルは論理学（というか記号論理学）の歴史という巨人の肩の上に乗ることで、パラドックスを形式化しました。
その手際は鮮やかです。
ゲーデルは論文にてこう書きます。
（引用開始）
どんな形式体系も、論理式は外見上、原子記号（変項、論理記号、括弧、句読点）の有限列であり、どの記号列が意味ある論理式であるか否かを正確に記述することは容易である。同様に、証明は、形式上（ある特定の性質をもつ）論理式の有限列に他ならない。もちろん、メタ数学的な考察においては、原始記号そのものがどんなものかは重要ではなく、われわれはこの用途に自然数を割り当てることにする。
すると、論理式は自然数の有限列、証明は自然数の有限列の有限列となる。こうしてメタ数学的概念（や命題）は、自然数や自然数の列についての概念（や命題）になる。（略）さて、以下では、体系PMで決定不能な命題、つまりAもnot-Aも証明できない命題Aを構成する。（略）以上の議論がリーシャルのパラドックスと類似していることが注目される。「うそつきのパラドックス」とも密接に関わっている。（脚注１４どんな認識論的パラドックスも、決定不能命題の存在論の同様な証明に使える）
（引用終了）（同上 pp.28-29,原論文では１－４及び１－５）
最後の部分は上記で引用したところです。
流れとしてはシンプルです。
整理しましょう。
１．論理式とは、原子記号の有限列である。原子記号とは（変項、論理記号、括弧、句読点）である。述語論理学を考えればたしかに変項と論理記号、括弧、句読点という原子記号があれば、すべての論理式が書けます。
２．その原子記号が配列された論理式のうちで、意味のある論理式と意味のない論理式は見分けられる。（端的に言えば文法に従わない文章は意味のない文章として取り下げられるというイメージです。ランダムに猿にタイプライターを打たせて、原子記号を並ばせた時、意味のある論理式＝命題と、意味のない論理式は区別がつくというイメージです）。
３．証明は論理式の有限列でしかない。論理式をある規則（アルゴリズム）に従って、演算していくのが証明です。記号論理学の証明というのは、ざっくり言えば中学校の授業で多項式の展開をするのと同じです（ゲームみたいなものです）。ですので、外見上は証明というのは、その意味を剥いでしまえば機械でも可能な機械的な操作であり、論理式の有限列でしかないということです。
という、下ごしらえをした上で、ここからゲーデルの技が光ります！
これらの原子記号に自然数列を当てはめていきます。このときの当てはめ方が素数の性質をフルに活かした見事で鮮やかなものです。
４．すると、論理式は自然数の有限列になります。そして、証明すらも自然数の有限列の有限列となります。その要素をすべて自然数列に当てはめるのですから当然と言えば当然ですが、すべての論理命題とその証明をすべて自然数として記述したのです。
その上でカントールが無限の濃度に関する証明で使ったカントールの対角線論法を利用して、自己言及のパラドックスを自然数論の枠の中で示します。それが「体系PMで決定不能な命題、つまりAもnot-Aも証明できない命題A」であり、ゲーデル数です。この決定不能な命題、すなわちAもNot-Aも証明できない命題（真ではない命題）が存在するということを示したのが不完全性定理です。
すなわち、「『プリンキピア・マテマティカ』およびその関連体系における形式的に決定不能な命題について Ⅰ」という論文のタイトルはまさに名は体を表わしています。
ちなみにこの論文は「Ⅰ」とあり、一作目であることが示されています。
K. Gödel Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38: 173-98. 1931
第２弾はより拡張して証明するつもりだったのでしょうが、チューリングに先をこされます。
原論文の附記にはこうあります。
（引用開始）
附記
（略）その後の発展の結果、とくにA.M.チューリングの仕事のお陰で、いまや形式体系の一般概念について厳密で、疑いなく妥当な定義が得られるようになり、それにより定理ⅥとⅪの完全に一般的な表現が可能になった。すなわち、つぎのことが厳密に証明される。ある程度の有限的算術を含むどんな無矛盾な形式体系にも決定不能な算術命題が存在し、さらにそのような体系の無矛盾性はその体系において証明できない。
（引用終了）
繰り返しになりますが、チャイティンはこう言いました。
「手短に言うと、ゲーデルは不完全性を、チューリングは計算不可能性を、私はランダム性を発見しました。」（引用はチャイティン、p.3)
ゲーデルは公理系のSyntaxとして不完全性定理を示しました。それはヒルベルトプログラムが破綻した瞬間でした。公理系とは論理学によって形式化された数学の純化と言えます。
しかしゲーデルにおいて、論理式の証明はすでに機械的な有限回の操作でしかないで、それは機械化できます（もちろんゲーデルは論理式とその証明が可算無限であるということがポイントだったのですが）。
チューリングは実際に証明を演算と考え、思考実験のコンピュータ（シンプルなアルゴリズムながら、無限のメモリを持つ原始的なコンピュータ）の停止問題として不完全性定理を読み替え、そしてチャイティンは停止確率という定数のランダム性をリアルなコンピュータの上で、Lispというプログラムを走らせることで証明しました。
チャイティンは高らかにこう言います。
（引用開始）
私は、神が、物理学ばかりでなく、純粋数学においても、自然数論においてさえ、サイコロをふることを証明した。
（引用終了）
これはもちろんアインシュタインの有名な逸話「"Der Alte würfelt nicht."神はサイコロを振らない」に対するものであり、ボーアは「"Einstein, schreiben Sie Gott nicht vor, was er zu tun hat."アインシュタインよ、神が何をなさるかなど、注文をつけるべきではない」と返したと言われますが（引用はWikipedia「ボーア」）、チャイティンは自分はサイコロを純粋数学でも自然数論でも、神はサイコロを降る（ランダム性は原理である）ということを証明したと自負しているということです。
よくある誤解に、不完全性定理が数学を不完全にしたとか、不確定性原理が物理学を不確定にしたというものがあります。もちろんこれは誤解であり、より厳密になった結果として、決定論ではなくランダム性が原理に組み込まれているのが我々の世界であることが示されただけです。
その意味では古典と呼ばれる物理学もそうですし、メタ数学以前の数学は現在の視点から言えばざっくりとした近似解であるということです。
というようなことを考えながら、久々に寺子屋「ゲーデルの不完全性定理」を復習してみてください。
今月はクリプキ様の完結編である「ウィトゲンシュタインのパラドックス」と電磁気学を新たな視点で再構築する「ファインマンの量子電磁力学」です。お楽しみに！
ちなみに、「アインシュタインよ、神が何をなさるかなど、注文をつけるべきではない」と諭したとされるボーアの紋章（Coat of arms)はこちら。
我々に馴染み深いシンボルがあります。
【書籍紹介】
これも繰り返し紹介していると思いますが、上記で引用したチャイティンの名著です。
知の限界/エスアイビー・アクセス
￥2,940
Amazon.co.jp
ゲーデルの不完全性定理の原論文をきちんと読むのであれば、これが一番ではないかと思います。
ゲーデルに挑む: 証明不可能なことの証明/東京大学出版会
￥2,730
Amazon.co.jp