有限の中の無限、無限の中の有限

先に見てきたのは、図の左側の n-exponential な時間で「検証可能」な複雑性を考えて、複雑性概念を拡張すると、ついには、「帰納的可算」のクラスに至るという話である。

n-exponential な数は、たとえそれがどんなに巨大なものであっても、有限な自然数であることに変わりはない。ただ、その有限の「無限」な連鎖の果てに、良く定義されたある意味自然な概念が、改めて、たち現れるのだ。

振り返ってみよう。

我々は、無限のものを認識できない。まず、認識の対象を形式的に有限な手段で定義可能なものに限る。「帰納的可算」というのは、そうした概念である。ただ、そこには、キチンと定義はできても、計算不可能だったり証明できないものが含まれる。

それで、「帰納的可算」の概念に手を入れ、キチンと定義され、かつ、計算可能なもの・証明可能なものを「帰納的」なものとして再定義する。「チューリング・マシンで実効的に計算可能なものが、計算可能である。」という「チャーチ・チューリングのテーゼ」は「計算可能性理論」（それは、「計算不可能性理論」でもあるのだが）の、ある意味、完成形である。

ただ、この「チャーチ・チューリングのテーゼ」の定義に従えば、「計算可能」であるはずなのだが、現実的には、どうしても計算できないものがたくさんあることに気付く。こうした実際には手に負えないものを、現実的に計算可能なものとを区別しようという動きが生まれる。「計算複雑性」の理論誕生の背景は、そうしたものだと思う。

こうして、「多項式時間」で計算できるものと、「多項式時間」では計算できないものとを区別しようという一つの基準が導入される。この基準は、ある意味合理的なものであった。1970年代に登場した複雑性理論は、コンピュータ・サイエンスの中心分野の一つとして発展し、成功する。それはいいことだ。

ただ、悪いニュースもある。いつの間にか、計算を科学する様々な分野に、次のような考えが生まれてくる。それは、もとの「チャーチ・チューリングのテーゼ」を修正した、「チューリング・マシンで多項式時間で計算可能なものが、計算可能である。」という考えが、「計算可能性」の定義として広まりはじめたことだ。それを「拡大されたチャーチ・チューリングのテーゼ」という。

「拡大されたチャーチ・チューリングのテーゼ」が、おそらく「誤り」であるだろうという、「傍証」は、近年の量子コンピュータ技術の発展による「量子優越性」の実験で示された。なぜなら、「量子優越性」というのは、「量子コンピュータで多項式時間で計算可能なものには、古典的コンピュータでは多項式時間で計算できないものが含まれている」ということだからである。例えば、素因数分解がその例だ。

量子コンピュータで「多項式時間で計算可能」なものと、古典的コンピュータで「多項式時間で計算可能」なものとが一致しないのなら、「計算可能性」の定義は「多項式時間」という規定だけでは、一意には決まらないのだ。（ここで「古典的コンピュータ」というのは、我々が日常的に使っている普通のコンピュータのことで、その計算能力は「（古典的）チューリング・マシン」に等しい。）

おそらくは誤りである「拡大されたチャーチ・チューリングのテーゼ」への拝跪は、我々の認識の「限界」（もちろん、計算科学の内部での話だ）を「多項式時間」と等置する傾向を生み出してきたのではないかとも感じている。

確かに、PとNPの関係では、NPも「多項式時間で検証可能なクラス」として「多項式時間」で限界づけられている。また、全ての証明可能な数学的命題が、NP-完全のクラスに属するにのだから、「多項式時間」を数学的認識の「限界」とみなすことは、充分、合理的でもあるように見える。

ただ、前回まで見てきた、MIP*=REに結実するアプローチは、「多項式時間で検証可能なクラス」の束縛をはずしたことで可能となったことに、注意が必要だと僕は考えている。

次回、無限について初めて自由に考えた数学者カントールの、超限順序数の構成を紹介しようと思う（図の右側）。ここでのωは、自然数全体を表す。左のべきは、2についてだが、こちらは、もっと巨大な数のべきである。それにも関わらず、両者は、よく似ていると僕は思う。

驚くべきことに、このイプシロン・ゼロは、可算なのだ。無限の拡大を究極まで進めたとしても、我々は、可算無限を超えることは難しいのだ。そして、それは「証明可能性」について、驚くべき洞察を可能にする。ゲーデルの不完全性定理が禁じた「自然数論の無矛盾性証明」が可能となる。

おそらく、「多項式時間」の拘束に拘泥せず、無限について自由に考えることが、我々の数学的認識を豊かに広げる鍵の一つだと、僕は考えている。