自己言及の定理（ゲーデル）

ゲーデル・エッシャー・バッハの3人目の重要人物はK・ゲーデル。ゲーデルは不完全性定理の証明の過程で自己言及のパラドックスをうまく回避しつつ自己言及を可能にするテクニックを編み出しました。

自己言及は時にとんでもないパラドックスを引き起こします。たとえば、有名なのはエピメニデスのパラドックス（うそつきのパラドックス）です。クレタ人のエピメニデスはこう言いました。

クレタの人はみなうそつきである。

クレタ人のエピメニデスがクレタ人のことを語っている（自己言及）のでややこしいことが起こります。

もしこの文章が本当（クレタ人はみなうそつき）だと仮定するとクレタ人はみんなうそつきになります。つまり、この文章を語ったクレタ人のエピメニデスもうそつきです。その結果、「クレタ人はみなうそつきである。」はうそになります。つまり、クレタ人はみなうそつきでないです（元の仮定がひっくり返ってしまった！）。クレタ人はみなうそつきでないとなると、クレタ人のエピメニデスもうそつきでないです。つまり、エピメニデスの言った「クレタの人はみなうそつきである。」は本当になります。つまり、クレタ人はみなうそつきです。（またまたひっくり返ってしまった！）。これが無限に続きます・・・あー頭がおかしくなりそう。

これと同じパラドックスは次の文章でも見られます。

私はうそをついている。
この文は誤りである。

上に共通しているのは、自分が自分自身に語るときにパラドックスが生じるってことです。そして、ゲーデルの不完全性定理も、数論の命題が数論の命題について語るという形を取ります。

ゲーデルの不完全性定理
数論の無矛盾な公理系は、必ず決定不能な命題を含む。

この定理は、数論を使って数論の性質を証明しようとしてます。つまり、自分自身の性質を証明しようとしてるわけです。数論ってのは整数に関する命題であって、数論に関する命題ではありません。つまり、数論の命題は整数について語れるが、数論の命題自身については語れません。ここで、ゲーデルは数論の命題を整数でコード化できれば数論の命題が数論の命題について語れるってことを見抜いたんだそうです。数論の命題を整数にコード化する方法はゲーデル数と言います。

このコード化というテクニックはコンピュータの分野では今や当たり前です。かつてプログラムはデータを操作するものであって、プログラムは操作できないはずでした。しかし、現在のコンピュータの基本原理であるプログラム内蔵方式では、プログラム自体をデータと同じ表現方式でコード化します。またプログラミング言語LISPもプログラム自体をデータと同じリスト表現でコード化します。こうすることでプログラム自体をプログラムで操作できるようになるんですね。こういうテクニックはメタプログラミングと呼ばれてます。

ゲーデル・エッシャー・バッハでもゲーデルの定理はかなり詳しく語られるそうですが、下の本も参考文献として上げられています。

ゲーデルは何を証明したか―数学から超数学へ