「不完全性定理とはなにか」を読みました

「不完全性定理とはなにか　ゲーテルとチューリングの考えたこと」(竹内薫著、ブルーバックス)を読みました。 たまには情報学には直接関係無さそうな分野の内容でも知ろうかと思い、前々から気になっていた不完全性定理について書かれた本を読みました。この本にはチューリングの停止性問題の話も乗っていたので、結局は無関係ではなかったのですが。 内容は非常に読みやすく、最近はとんと数学に触れていなかった私にも比較的すんなりと理解出来ました。論理学についての初歩的な知識は必要かもしれませんが、その辺りも丁寧に解説されています。 正直、未だに狐につままれたような感じで100%理解できたとは思えませんが、それでもゲーデルの不完全性定理の概要は掴めたように思います。また、チューリングの停止性問題も大学の講義ではさらっと流していましたが、ゲーデルの不完全性定理と同様のロジックで説明ができると知り、大変勉強になりました。 ゲーデルの不完全性定理とチューリングの停止性問題は、ともに対角線論法という手法で説明ができるようです。対角線論法というものを私は本書で初めて知りましたが、無限やらの難しい概念が絡む問題を非常にシンプルに証明できていて驚きました。詳しい説明は本書を読んでいただきたいですが、無限に存在するはずの自然数は、0以上1未満の実数の総数より少ない、というにわかには信じがたい問題を対角線論法を用いることで簡単かつ明確に説明出来ます。 時間があったら竹内氏が巻末で紹介している文献も読んでみたいと思います。