チャーチ＝チューリングのテーゼ

チャーチ＝チューリングのテーゼとは、計算できる関数はすべてチューリングマシン（または等価な形式システム）によって計算可能であるという命題であり、計算可能性の概念の核心をなす。ダグラス・ホフスタッターは著書『ゲーデル、エッシャー、バッハ』において、このテーゼが「機械的な手続きで解決できること」と「知性が行うこと」の関係を問う上で中心的な意味を持つと論じた。

チャーチ＝チューリングのテーゼの誕生

1936年、アラン・チューリングとアロンゾ・チャーチはそれぞれ独立に「計算とは何か」を形式化した。チューリングは「チューリングマシン」という抽象的な計算装置を定義し、チャーチは「ラムダ計算」という計算の形式体系を開発した。両者が等価であることが後に示され、「計算可能な関数はすべてチューリングマシン（またはラムダ計算）で計算できる」というテーゼが確立した。

このテーゼは定理ではなく「テーゼ（主張）」であることが重要だ——証明できないが、今日まで反例が見つかっていない。チューリングマシンを超える計算能力を持つ物理的なプロセスが存在するかどうかは、量子計算・アナログ計算などの文脈で今も探求されている。

チャーチ＝チューリングのテーゼが使われた時代

コンピュータ科学の基礎として、チャーチ＝チューリングのテーゼは計算可能性理論・複雑性理論・プログラミング言語理論の礎となった。「何が計算できて、何が計算できないか」——停止問題の決定不可能性など、チューリングマシンの理論が示した「計算の限界」は、コンピュータが何に対して「答えを出せないか」の構造的理解を与えた。

不完全性定理との深い関係も重要だ。ゲーデルの不完全性定理とチューリングの停止問題の決定不可能性は、互いに類比的であり、形式体系と計算の根本的な限界を示す双子の発見として理解できる。どちらも「自己言及」という構造を中心に置いており、自己言及性というホフスタッターの核心テーマと直結する。

現代における位置づけ

現代の量子コンピュータは、特定の問題（因数分解・量子シミュレーション）でチューリングマシンを指数的に上回る効率を持つ。しかし「計算可能性」の意味ではチューリングマシンと等価だとされる——量子コンピュータがチューリングマシンで解けない問題を解くわけではなく、一部の問題を劇的に速く解くだけだ。

チャーチ＝チューリングのテーゼの現代的な意味は、「人間の思考もチューリングマシンで原理的に模倣できるか」という問いだ。これは人工知能・意識・自由意志の問いと直結する。ペンローズは量子的プロセスがチャーチ＝チューリングのテーゼを超えた計算を行うと主張したが、多くの研究者から批判されている。

チャーチ＝チューリングのテーゼが残すもの

このテーゼが最も深く問うのは「知性と計算は同じか」だ。MIU体系・不完全性定理・人工知能の問いは、すべてチャーチ＝チューリングのテーゼという「計算の境界」をめぐる問いの変奏として読める。計算の限界を知ることは、知性の可能性と限界を知ることでもある。

不完全性定理が開いた扉

不完全性定理は、数学の失敗ではなく、人間の知性の地図を描き直した偉業だ。ゲーデル・エッシャー・バッハが示すように、自己言及は破壊ではなく創造の源でもある。メタ数学の問いは「数学で何が証明できるか」という問いから「思考とは何か」という問いへと発展した。人工知能研究者はゲーデルの定理を繰り返し参照し、機械が「理解する」とはどういうことかを問い続けている。数学の限界を示した定理が、知性の可能性の探求を最も強力に駆動してきたのは、歴史の逆説だ。