チューリング完全とは何か（第2回/全3回）

第1回では、チューリングマシン（TM）をゼロから構築した。テープ、ヘッド、少しばかりの状態と遷移。回文検出器はせいぜい十数個の状態だった。

このシリーズのきっかけとなったのは、デミス・ハサビスの「人間の脳（およびAI基盤モデル）は近似チューリングマシンである」という発言だった。しかしハサビスは、私たちの心が小さな回文検出器のようなものだと言いたかったわけではないだろう。彼が主張していたのは計算能力についてだ。脳は、十分な時間（計算資源）とメモリがあれば、計算可能なものすべてを計算できる。この性質を表す専門用語がチューリング完全である。

万能チューリングマシン

第1回では、問題ごとに個別のマシンを構築した。回文用に1台、偶数カウント用に1台。それぞれが1つのタスク専用に設計された固定装置だった。素数判定をしたい？新しいマシンを作る。数値をソートしたい？また別のマシンを作る。

そこでチューリングは問いかけた。すべてのマシンの仕事をこなせる1台のマシンを作れないだろうか？

答えはイエスだ。万能チューリングマシン（UTM）とは、別のマシン $M$ と入力 $w$ のエンコーディング $\langle M, w \rangle$ を受け取り、$M$ が $w$ 上で実行される様子をシミュレートする特定のチューリングマシン $U$ のことだ。

$$U(\langle M, w \rangle) = M(w)$$

エンコーディングはテープ上のデータに過ぎない。状態を数値として、遷移テーブルをルールのリストとして、そして入力 $w$ を記述する。UTMはこの記述を読み取り、$M$ の状態、ヘッド位置、テープ内容を自身のテープ上で追跡しながら、ステップごとに実行していく。

「プログラム」という用語はここから来ている。UTMはタスクごとに再構築する必要がない。異なるプログラム（つまりエンコーディング）を与えるだけでいい。あなたのノートパソコンも同じ仕組みで動いている。実行するPythonスクリプトがエンコードされたマシン $M$ であり、それに与えるファイルが入力 $w$ であり、CPUが $M$ を $w$ 上でステップごとにシミュレートする。

チューリング完全性

チューリングはUTMを物理的に構築したわけではない。構築できるほど精密に仕様を定めたのだ。その仕様自体が証明となっている。他のどんなマシンでもシミュレートできる具体的なマシンを示したのだ。この能力を持つあらゆるシステムをチューリング完全と呼ぶ。エンコーディング $\langle M, w \rangle$ を与えれば、$M$ が $w$ に対して行うことを何でも実行できる。

チューリング完全になるには何が必要か？3つのことだ。

1. 無制限の読み書きメモリ：制限なく拡張できるストレージと、任意の場所への読み書き能力（TMの無限テープと読み書きヘッドのように）
2. 条件分岐：データの値に基づいて異なる動作をする能力（遷移関数のように「状態 $q$ で $s$ を読んでいるなら...」）
3. 無制限の反復：ループ、再帰、またはそれに相当するものによって、操作を無限に繰り返す能力（TMは必要な回数だけ状態を循環できる）

それで十分だ。Pythonにはこれらがある。JavaScript、C、Excel（嘘じゃない）、そしてPowerPointにさえある。エンコーディングは馬鹿げたものになるかもしれないが、ちゃんと動く。

天井

しかし、チューリング完全はシステムが到達しうる最大の能力なのだろうか？もっと強力なもの、つまりチューリングマシンでは解けない問題を解くシステムを構築できないだろうか？

チューリングマシンは関数を計算する。入力 $w$ を与えると、出力 $M(w)$ を生成する（または永遠に実行し続ける）。「計算可能な関数」の定義は形式化の方法によって異なる。チューリングはテープとヘッドのモデルを発明した。独立して研究していたアロンゾ・チャーチは、純粋関数を使って計算を定義した。他の研究者たちも独自の定義を提案した。驚くべきことに、あらゆる妥当な形式化がまったく同じ関数のクラスを定義することが判明した。出発点は異なれど、到達点は同じだった。

この収束がチャーチ=チューリングのテーゼを支持する証拠となっている。

関数が効果的に計算可能であるのは、それがチューリングマシンで計算可能である場合に限る。

反例は一度も見つかっていない。

このテーゼは私たちの問いに答えてくれる。チューリング完全性を超えた「スーパーコンピュータ」は存在しない。より高速なシステム、より使いやすい構文を持つシステムは作れる。しかし、チューリングマシンが計算できる以上のことを計算するシステムは作れない。

チューリング完全性が天井なのだ。

デミスの話に戻ろう

脳とニューラルネットワークはチューリング完全だ。分岐し、ループし、必要に応じてメモリを拡張できる。理論上は、どんな計算可能な問題でも解ける。

「汎用知能」とは、単にそれらの問題を十分に解くということだ。いくつ解けば十分かは、定義次第だ。現在のAIとその目標との差は、根本的な能力の問題ではない。十分な数の計算可能な問題を効率的に解けるかどうかの問題だ。人間とAIが「近似」チューリングマシンなのは、有限だからだ。チューリングマシンには無限のテープと無制限の時間があるが、私たちには固定されたパラメータと締め切りがある。しかし、私たちが本当に気にかける問題に対しては、効率さえうまく扱えれば、有限で十分なはずだ。

まだわからないのは、そこに至る最速の道だ。より良いデータ？より多くの計算資源？よりスマートなアーキテクチャ？おそらくすべてだ。何千人もの研究者と何十億ドルもの資金が、まさにこの問いに日夜取り組んでいる。

次回予告

チューリング完全性は、何が可能かを教えてくれる。しかし、何が不可能かは教えてくれない。

第3回では、天井を開けてその上を覗いてみよう。証明により解決不能な問題が存在する。単に難しいのではなく、どんなチューリングマシンでも、どんなコンピュータでも、どんな脳でも、どんなAIでも不可能な問題が。

この記事はClaude（Opus 4.5）と協力して執筆しました。