不完全性定理

角谷 良彦(情報理工学系研究科コンピュータ科学専攻 助教)

不完全性定理は,1930年頃にクルト・ゲーデル(Kurt Gödel)によって発表された定理であり,今日でもなお,この定理に魅せられて数学や哲学の道を歩む者は少なくない。数学とは公理から推論を積み重ねていくものであるというのが,近代数学の基本的な考え方であるが,そのような数学のあり方に大きく貢献したのがダフィット・ヒルベルト(David Hilbert)である。ヒルベルトはこの考えを押し進め,最終的に,数学を完全に公理化することや,数学が矛盾していないことを有限の立場から証明することを目指したが,不完全性定理の登場によってその夢は否定されることとなった。

第一不完全性定理の内容は,「数学を矛盾なくどのように形式化しても,証明も反証もできない命題が存在する」というものである。言い換えれば,数学に必要なすべての公理を書き出すことは不可能であるということになる。この定理がわざわざ第一と冠されているからには,第二不完全性定理なるものも存在する。第二不完全性定理は,「どのような形式的体系も,その体系自身が矛盾していないことを証明できない」というものである。こちらは,ある形式的体系が矛盾していないことを示すには,メタ論理として,その体系よりも強力な体系が必要であるということを意味している。

ところで,第一不完全性定理のいう命題とは,自分自身が証明不可能であることを意味するような命題のことである。これは,「この文は正しくない」という嘘つきのパラドックスに出てくる文とひじょうによく似た構造をしている。自己言及はしばしばパラドックスを引き起こす反面,不完全性定理で利用されているように興味深い性質を示すことも多い。情報科学は,自己言及を避けることなく,積極的に活用している分野のひとつである。

情報科学の研究対象であるプログラミング言語の多くは,再帰的プログラムとよばれる自己を参照するプログラムを構文的に許している。勿論,プログラミング言語が実装されている以上,再帰的プログラムも挙動は定まっているのだが,その抽象的意味は自明ではない。著者の所属する理学部情報科学科および,情報理工学系研究科コンピュータ科学専攻では,再帰も含めて計算というものの本質をとらえ抽象化する研究を行っている。