いまさら不完全性定理と人工知能について

人間の心を実現する人工知能は作れないとか人間は機械ではないことが不完全性定理から導かれるという主張(とそれに対する否定・批判)がしばしば行われてきた。議論の根本の部分は単純なので、そのあたりについてのメモを書いておく。特に目新しい議論や主張はない。
この主張でたぶん一番有名なのはルーカスの"Minds, Machines and Gödel"(1961)という論文。

簡単な算術ができて無矛盾であるどんな機械が与えられても、その機械から真として出力されないような式——つまりそのシステムで証明できない式——が存在する。しかしその式を我々は真だと理解できる。よってどんな機械も心の完全で適切なモデルになれず、心は本質的に機械とは異なる。
(J. R. Lucas "Minds, Machines and Gödel")

また高橋昌一郎『ゲーデルの哲学』(1999)には、ルーカスと同様のことをゲーデルも考えていたとする文章が出てくる。

帰結2 数学が主観的数学ならば、人間は有限機械と同等である。(機械論)
[中略]帰結2に不完全性定理を適用すると、人間精神は、自己の不完全性に直面し、「人間精神の機能を完全には理解しえないこと」になる。しかし、ゲーデルは、彼自身の人間精神によって、不完全性定理を証明することができた。つまり、彼は、主観的数学を上回る客観的数学の事実を証明したことになる。したがって、明言してはいないが、ゲーデルが帰結2を否定していることは明白である。
(高橋昌一郎ゲーデルの哲学』講談社現代新書 p.170)

ルーカスとペンローズの主張は、一言でいうと、テューリング・マシンの限界を示すこれらの定理を証明した人間は、テューリング・マシンよりも優れているということになる。この点は、ギブス講演で明言はしなかったが、ゲーデルが推論に組み込んでいた主旨でもある。彼らは、不完全性・非決定生・停止定理を証明するためには、アルゴリズムに還元できない思考力が要求されると考えるわけである。
(高橋昌一郎ゲーデルの哲学』講談社現代新書 pp.231-232)

ただし『ゲーデルの哲学』で翻訳・引用されているゲーデルの文章を見ると、ゲーデルは実際には上の文章のようには主張していない。これについては後で扱う。
またグレッグ・イーガン「オラクル」でも同様の議論が(否定的な扱いで)登場する。

ルーカスやそれに類似する議論を聞くと、(結論が正しいかどうかはともかく)推論の過程に明白な間違いは無いような感じがする。その一方で、やはり何かおかしな感じがする。不完全性定理の証明(やそれを紹介したもの)を読んでも、それが「アルゴリズムに還元できない思考力が要求される」ような事をやっているようには思えない。

不完全性定理の証明

ルーカス(やその類似)の議論は不完全性定理を利用した議論なので、不完全性定理自体の証明の概略を見ておく。
無矛盾であり少なくとも簡単な数の計算は可能な公理系Tがあるとする。このとき不完全性定理は次のように証明される。

  1. 公理系Tから、「この文はTで証明できない」という文があることが示せる(対角化定理により)。この文をGと呼ぶことにする。
    \qquad T\vdash G \leftrightarrow \neg {\rm Provable}_T("G")
  2. 文Gが公理系Tから証明できると仮定してみる。
    次のように仮定してみる  \qquad T \vdash G
  3. 仮定2と述語Provableの性質により、「文GはTで証明できる」も公理系Tで証明できる。
     \qquad T \vdash \rm{Provable}_T("G")
  4. 一方で1と仮定2から、「文GはTで証明できない」も公理系Tで証明できる。
     \qquad T \vdash \neg \rm{Provable}_T("G")
  5. 3と4によりTで矛盾\bot(ある命題とその否定の連言)が証明されてしまう。
     \qquad T \vdash \bot
  6. よって(公理系Tは無矛盾だと前提したので)仮定2は間違い。文Gは公理系Tで証明できない。
     \qquad T \not\vdash G
  7. 文Gは「この文(=G)は公理系Tで証明できない」を表しているので、6により正しいことを表している。
    つまりGは正しいが公理系Tでは証明できない。

ルーカスの議論

ルーカスの議論はだいたい次のようなもの。

  1. もしも人間の心をチューリングマシンで実現できるなら、そのチューリングマシンで証明できる(出力できる)定理だけを証明するような公理系Tがある。この公理系Tは人間の心の仕組みを反映していると考えられる(この部分についても批判は色々ありえるけど、今回の本題ではないので非常におおざっぱな要約で済ませた)。
  2. 公理系Tに不完全性定理を適用すると、そのTで証明できない文Gが得られる。
  3. しかし、そのGが正しいこと(それを示す不完全性定理の証明)を人間は理解できる。
  4. よって人間の心は公理系Tを越えており、公理系Tは人間の心を実現できていない。

批判

ルーカスの議論のもっともらしさは、不完全性定理の証明や理解にはアルゴリズムを越える何かが必要であるという印象を相手に与えることで成立している。でもそれは間違っている。
不完全性定理そのものは公理系の内部で(ということはチューリングマシンで)も証明することができる(これは第2不完全性定理の証明の基本部分でもある)。上の不完全性定理の証明で証明されたことは

公理系Tが無矛盾なら、GはTで証明できない。
 \qquad T \not\vdash \bot \Rightarrow T \not\vdash G

ということであり、これを形式体系内で表現した式 \neg \rm{Probable}_T("\bot") \to \neg \rm{Probable}_T("G")はTで証明できる。
これに限らず不完全性定理で証明されていることはおおむね「公理系Tが無矛盾なら〜」という条件節が暗黙についている。そしてそれらの条件節付きの言明を形式体系内の式で表現したものは、形式体系がある程度強ければその形式体系内で証明できる。
なので、機械に証明できないことを人間が知ることができるのかという問題は、人間を表現すると仮定される公理系の無矛盾性の問題に帰着する。
第2不完全性定理によりTの無矛盾性をTで証明することはできないけれど、無矛盾性に対して人間は何が言えるのか。ルーカスに対する批判の多くが系の無矛盾性に焦点を当て議論を行っている。でも、そこに深入りしなくても良い。なぜなら

「この文はTで証明できない」はTで証明できない。でも人間には「この文はTで証明できない」が正しいことがわかる(だって「証明できない」という主張が成立してるんだから)。だから人間の心はTとは異なる

と言われれば、何となくもっともらしいことが言われているという印象を受けるけど、

「形式体系Tは無矛盾であること」はTで証明できない。でも人間にはTが無矛盾であることがわかる。

と言われても、これは全然もっともらしい話でも明らかそうな話でもない。「人間はその公理系が無矛盾であることを信頼できるのだ」とか言っただけでは機械と人間の差を言ったことにはならないし、そもそも公理系Tに具体性がないからそれについて何が言えるのかも明らかなことではない。無矛盾性の問題はルーカスの元の議論よりももっと微妙な話になる。無矛盾性について何をどこまで知れるのかということ自体は面白い問題だけど、人間の心を機械で実現できるかという問題からはかなり遠のいている。
結局のところルーカスの議論が一見もっともらしく見えるのは無矛盾性について何が言えるかという微妙な点を暗黙のうちにスルーしているからで、実際にはルーカスの議論だけではたいした結論は得られない。

ゲーデルのギブス講演について

ゲーデルの哲学』でも紹介されているように、ゲーデルは1951年のギブス講演の中で人間が有限な機械と同等かということに言及している。でもその議論は、

不完全性・非決定性・停止定理を証明するためには、アルゴリズムに還元できない思考力が要求されると考えるわけである。
(高橋昌一郎ゲーデルの哲学』講談社現代新書 p.232)

と要約されるような議論ではない。

ゲーデルの議論を要約すると次のようになる。
真である数学的命題全体を客観的数学と呼び、証明できる数学的命題全体を主観的数学と呼ぶことにした上で、次のように仮定してみる。

  • 1. 主観的数学の全ての定理を生み出す有限的な規則がある。

1は、(主観的数学を行う)人間の心が有限の機械と同等だと仮定している。
有限の機械には不完全性定理を適用できるので、仮定1と第2不完全性定理から次の結論が得られる。

  • 2. 主観的数学の規則から導かれる命題の全てが真であることを、数学的確実性をもって知ることは不可能である。(主観的数学の規則が無矛盾であることは主観的数学の定理としては得ることができないから)

結論2から次が言える。

  • 2-1. 人間の心は自分自身の機能を完全には理解できない。
  • 2-2. 人間の心が行う主観的数学では決定できないような数学的真理が存在する。(形式体系の無矛盾性は、ある多項式に整数解があるかという問題に翻訳される。主観的数学の規則の無矛盾性に対応する多項式問題は主観的数学の規則では解くことができない)

1 → 2 → 2-2 となり、1から2-2が導かれるので、次のうち少なくとも一方は正しい。

  • (A)人間の心はどんな有限機械よりも優れている(1の否定)。
  • (B)絶対的に解決不可能な多項式問題が存在する(2-2)。

もちろん人間機械論・反機械論にとって重要なのはAだけど、ギブス講演では数学的プラトニズムの正当化の議論にBを利用することに重点が置かれている。そのためギブス講演の議論をそのまま用いるだけでは、人間は機械ではないという主張の擁護にはならない。
(もっと詳しい議論については『ゲーデルと20世紀の論理学1』(2006)の飯田隆「不完全性・分析性・機械論」と、『ゲーデルと20世紀の論理学4』(2007)の戸田山和久ゲーデルプラトニズムと数学的直観」)