複雑性理論と人工知能技術（２） チャーチ＝チューリングのテーゼ

複雑性理論は、もともとは、「計算とは何か？」「計算可能なものとは何か？」という問いから生まれたものである。この分野の代表的な成果は、ゲーデルの不完全性定理なのだが、それは、1930年だから、90年近く昔の話だ。

ただ、この不完全性定理は、確かに驚くべきものではあるのだが、ほとんど役に立たない定理である。

というのは、言い過ぎなのだが、この定理から、我々人間の（同時に、それは人工知能にとっての）認識能力の限界を議論するのは、あまりに、荒い議論であると僕は考えている。

一つには、不完全性定理による原理的な「限界」以外にも、形式的演繹による認識には、実質的には、様々な「限界」が存在しているからだ。我々の形式的認識の「限界」を構成しているのは、不完全性定理だけではないのだ。複雑性理論は、もっと精緻に、その「限界」を境界づけようとしている。
あと一つには、不完全性定理は、「証明不可能性」「形式的体系の無矛盾性」についてのショッキングな定理なのだが、いかなる計算、いかなる証明が「可能」であるかについては、あまり、多くのことを我々に教えてはくれないのだ。
歴史的に見ると、不完全性定理は、証明あるいは計算の性質についての探求の中で生まれた「最後の結論」ではないのだ。事実は、その逆である。1930年代に、この分野は、不完全性定理に強烈な刺激を受けて、「証明とは何か？」「計算とは何か？」という基本的な「問い」に突き進むことで発展する。
知的な展開としては、それに少し先行した、ハイゼンベルグやシュレジンガーやディラックといった若い天才たちが大活躍した量子力学の基礎付けの時代と比肩しうる、エキサイティングな「知的な黄金時代」だったと思う。（現代は、本当に、「イノベーティブ」なのかと、ふと思う。）
ゲーデル＝エルブランの「帰納関数論」、チャーチの「ラムダ・カリキュラス」、チューリング＝ポストの「チューリング・マシン」が続々と登場する。この時代の白眉は、これらの「計算可能性」についての見かけは全く異なるアプローチが（もちろん、それは、ゲーデルの結果を再現できるものだ）、次々と、「同値」であることが証明されていくことだ！
1940年代には、今日、「チャーチ＝チューリングのテーゼ」と呼ばれる「計算可能性」についての認識は、確立されることになる。これが、「複雑性理論」の第一世代である。
【次につづく】
以下の議論は、読み飛ばしてもらって、構わない。

多くの人は、ゲーデルの結果から、初等数論の無矛盾性は証明できないと考えているのだが、ゲンツェンは、ε0までの超限帰納法を使って、初等数論の無矛盾性を証明している！

初等数論の無矛盾性は、証明できるのかできないのか？

こうした奇妙な問題状況を理解するのにも、「多項式時間」と「指数関数時間」を区別する複雑性の議論は役に立つように思う。

ゲーデルの証明は、ヒルベルト流の「有限の立場」に立つものだが、ゲンツェンの証明は、可能な証明のパターンの枚挙に、指数関数的に増大する手間をかけている。ε0というのは、可算無限に可算無限回べき乗の操作を繰り返した、指数関数的増大の権化みたいな数だ。（それでも、「可算」なのだが）

ε0については、「楽しい数学：集合論入門」https://www.marulabo.net/docs/20180529-marulabo-math/　を参照してほしい。