普遍チューリングマシン

普遍チューリングマシンとは、他のどんなチューリングマシンの動作もシミュレートできる、ただ一台のチューリングマシンのことである。数学者アラン・チューリングが1936年の論文で示したこの構想は、「計算する手続き」と「その手続きが処理するデータ」を同じ土俵の上に置くという、当時としては見過ごされがちな発想に基づいていた。この単純な発想が、今日のあらゆる汎用コンピュータの理論的な原型になっている。

決定問題から生まれた着想

1936年、チューリングは論文「計算可能数について」で、ヒルベルトが提起した決定問題――あらゆる数学的命題の真偽を機械的に判定する手続きは存在するか――に取り組んだ。その道具として考案したのが、テープ上の記号を規則に従って読み書きする単純な仮想機械、チューリングマシンである。個々のマシンはそれぞれ特定の計算しか行えないが、チューリングはさらに、あるマシンの動作規則とその入力を、ともに記号列として符号化しテープに書き込めば、それを読み取って元のマシンと同じ計算を再現できる特別な一台を作れることを示した。これが普遍チューリングマシンである。同じ頃アロンゾ・チャーチが別の形式で示した計算可能性の定式化と合わせ、後にチャーチ＝チューリングのテーゼとしてまとめられていく。

プログラムをデータとして扱うという発想

普遍チューリングマシンの核心は、「機械の設計図」と「機械が処理する入力」を区別しない点にある。それまで、計算を行う装置とその装置が扱う対象は別々のものと考えるのが自然だった。チューリングは、他のマシンの動作規則を単なる記号列としてテープに書けることに気づき、それを読み込んだ普遍マシンが元のマシンとまったく同じ動作を再現できると示した。「手続き(プログラム)もまたデータである」というこの洞察が、ハードウェアとソフトウェアを分離し、回路を作り替えずにプログラムの書き換えだけで別の計算を行うという、現代のコンピュータの根本原理の原型になった。

ハードウェアとソフトウェアの起源

アンドリュー・ホッジスによる評伝『チューリング——コンピュータ科学の父』は、この着想を単なる数学的技巧としてではなく、コンピュータ科学そのものの出発点として描いている。本書は普遍チューリングマシンを、「プログラムを記述するコンピュータ」という発想を初めて形式化したものと位置づけ、戦後にフォン・ノイマンらが実装したフォン・ノイマン・アーキテクチャ――命令とデータを同じメモリに格納するストアドプログラム方式――の直接の原型として描き出す。理論的な証明と実機の誕生のあいだには十年余りの隔たりがあるが、両者を貫く原理は同一である。

万能性の裏にある限界

普遍性を示したのとほぼ同じ論文で、チューリングは決定問題そのものには否定的な結論を導いてもいる。あるチューリングマシンが与えられた入力に対していつか停止するかどうかを、あらゆる場合について判定するアルゴリズムは存在しない(停止問題)。何でもシミュレートできるという普遍マシンの圧倒的な力と、その挙動を外側から完全には見通せないという限界は、実は同じ論文・同じ枠組みから生まれた表裏の結論である。

なぜ今、普遍チューリングマシンなのか

手のひらのスマートフォンもデータセンターのサーバーも、原理的には普遍チューリングマシンの物理的な近似にすぎない。専用の回路を作り替えなくても、ソフトウェアを入れ替えるだけで別の仕事をこなせるという「当たり前」は、1936年にチューリングが紙の上で証明した定理に由来する。画像認識であれ大規模言語モデルであれ、今日の人工知能も結局は同じ万能機械の上で走る一本のプログラムにすぎない。抽象的な論理パズルとして生まれた着想が、80年以上を経てなお計算文明の土台であり続けている事実は、理論的な洞察がどれほど射程の長い実用性を持ちうるかを物語っている。