Busy Beaver から現代 CPU へ：1936年の抽象が実際のシリコンになるまで
計算機科学には、チューリングにまつわる有名な物語が二つあります。ひとつは、計算可能性を定義した1936年の論文。もうひとつは、あまり語られない、あの抽象機械がいかにして手元のノートPCの中の温かい長方形になったか、という物語です。その二つのあいだに、ひとつ小さくも印象的な寄り道があります。それが Busy Beaver 関数 で、非計算可能性を手触りのあるものにしてくれます。
この記事では、計算可能性理論でもっとも「実用離れ」した対象から、キーボードの下で静かに動いているきわめて実用的なものまで、全体の流れをたどります。
パート1 — Busy Beaver：触れられる非計算可能性
その起源
1962年、ハンガリーの数学者 Tibor Radó は、当時オハイオ州立大学にいて、“On non-computable functions” を発表しました。彼には教育上の問題がありました。それ以前の非決定性の結果――停止問題や Rice の定理――は、すべて対角化法で証明されており、学生は理解できても、実感は持ちにくかったのです。Radó は、具体的で、有限で、直感的 でありながら、なお計算不能な関数を求めていました。
彼の発想は、ほとんど遊び心に満ちたものでした。n 個の状態を持ち、2つのテープ記号（0 と 1）を使い、かつ空白テープ上で最終的に停止するあらゆる Turing machine を考えてみましょう。状態名の付け替えを同一視すれば、そのような機械は有限個しかないので、次の2つの量が定義できます：
- Σ(n) — the maximum number of
1s any such machine leaves on the tape when it halts. - S(n) — the maximum number of steps any such machine takes before halting.
テープの上を小さなビーバーがせわしなく走り回り、止まる前にできるだけ多くの印を打つ様子を思い浮かべてください。そこからこの名前が付いています。
Why it isn’t computable
矛盾を仮定して、Σ が計算可能な全関数だとしましょう。すると、n 状態の任意の Turing machine M に対して Σ(n) を計算し、M を Σ(n) + 1 ステップだけシミュレートすれば、それが停止したかどうかを判定できます。これは、私たちが非決定可能だと知っている停止問題を解いてしまうことになります。したがって Σ は、あらゆる計算可能関数を必ず追い越します。
実際、Σ の成長は非常に速く、やがてプログラムで書けるどんな関数も上回ってしまいます。これは「計算不能だが、定義は明確」という典型例です。
The numbers that we know
小さな値を確定させることさえ極めて難しく、新しい n が1つ増えるたびに探索空間は桁違いに膨れ上がります：
| n | Σ(n) | Year settled |
|---|---|---|
| 1 | 1 | 1962 |
| 2 | 4 | 1962 |
| 3 | 6 | 1965 |
| 4 | 13 | 1983 |
| 5 | 4098 | 2024 (formal proof in Coq, bbchallenge) |
| 6 | ≥ 10↑↑15 | open |
Σ(5) から Σ(6) への跳躍は漸進的ではなく、Knuth の上矢印記法へと落ち込む断崖です。Σ(6) は、私たちの宇宙で物理的に意味を持ちうるあらゆる数よりも大きいと予想されています。
The lesson Radó delivered
計算可能性の外へ出るのに、奇抜な構成は必要ありません。テープを持つ有限状態機械――まさに Turing が発明したその対象――の中に、アルゴリズムでは固定できない関数がすでに隠れています。計算の限界は遥か彼方にあるのではありません。n = 5 のところで姿を現すのです。
この点を覚えておいてください。Turing machine は、非自明な最も単純なコンピュータであると同時に、この分野で最も深い不可能性結果を運ぶ器でもあります。では、その同じ対象がどのようにしてあなたの CPU になったのかを見ていきましょう。
Part 2 — A Common Misconception: “How Many States Is a Modern Chip?”
Busy Beaver を知ると、自然にこんな疑問が浮かびます。Turing machine を状態数で測るなら、たとえば M3 や Ryzen は何状態なのか？ いかにも答えられそうですが、実際には答えられません。そして、その理由は示唆に富んでいます。
Mistake 1: “States” is two-dimensional
Busy Beaver ではアルファベットを2記号に固定し、状態数 n だけを変えます。しかし Turing machine には 状態数 n と 記号数 k の両方があります。2記号 Busy Beaver、3記号 Busy Beaver、その先の各バージョンがそれぞれ独自の表を持っています。(n, k) の組み合わせの対応は単純ではなく、「状態数」だけでは普遍的な複雑さの尺度にはなりません。
Mistake 2: A CPU isn’t a Turing machine
実際の CPU は 有限のメモリ しか持ちません。レジスタ、キャッシュ、RAM 全体で B ビットの状態があるなら、機械全体の構成数は最大でも 2^B 通りです。厳密には、これは巨大な 有限状態機械、あるいはディスクまで含めて RAM を有界とみなすなら linear bounded automaton (LBA) であって、Turing machine ではありません。欠けているのは、まさに無限のテープです。
ほとんどの用途では、現代のコンピュータを Turing complete だとみなします。その上限は実用上あまりにも遠く、無視しても何も困らないからです。しかし理論的には、いいえ、あなたのノートPCは Turing machine ではありません。
Mistake 3: Bits of state ≠ controller states
たとえ有限状態機械として捉えても、Busy Beaver の「状態」は機械の 制御部 に対応します。つまり、次の動作を選ぶ小さな switch-case のようなものです。実際のチップが持つ巨大な 2^B 通りの構成空間の大半は、制御側ではなく テープ側（レジスタとメモリ）にあります。これらを混同するのは、本の複雑さをインクのあらゆる配置の数で測るようなものです。
What’s the good question?
本当に数値が欲しいなら、知りたい次元を選ぶべきです：
- 制御系の複雑さ？ → 現代の x86 の microcode ROM には、およそ 10⁴〜10⁶ のマイクロオペレーションが入っています。これは「制御状態」の有用な見積もりです。
- トランジスタ数？ → フラッグシップ級のダイでおよそ 10¹¹ 個です。
- シミュレーションコスト？ → CPU 1秒分をシミュレートするのに Turing machine のステップ数はいくつ必要か？ ワークロードにもよりますが、およそ 10¹⁰〜10¹² ステップです。これは理論的に最も意味のある問いです。
どの答えも、何かしら実在するものを測っています。「私の CPU は何状態か？」という問いは、見た目は明快ですが、精査すると崩れてしまいます。理論からハードウェアへの対応は、数値ではなく構造です。
Part 3 — How Turing Machine Ideas Actually Live in a CPU
ここからが核心です。Turing machine には4つのプリミティブがあります。それぞれは現代のハードウェアにきれいに対応しますが、同時に理解しておくべき明確な逸脱もあります。
The four-element mapping
| Turing machine | 現代のコンピュータ |
|---|---|
| 無限テープ | RAM + ディスク + ネットワークストレージ |
| 読み書きヘッドの位置 | メモリアドレス（PC、スタックポインタ、MMU の変換） |
| 有限状態の制御器 | CPU の制御ユニット + microcode ROM |
| 遷移関数 δ | Instruction Set Architecture (ISA) + デコーダ |
この表は骨格にすぎません。面白いのは、工学が抽象からどこで逸れていくかです。
The key conceptual leap: the Universal Turing Machine
Turing の1936年の論文には大きなアイデアが二つありますが、よく知られているのは実は二つ目の Universal Turing Machine (UTM) です。UTM とは、テープ上に別の Turing machine の記述――と、その機械への入力――を受け取り、それをシミュレートする Turing machine です。
この瞬間に、「機械」は「データ」になります。計算の記述そのものが記号列であり、計算が処理するデータと種類のうえでは区別できません。これが stored-program computer の概念的な種子です。
フォン・ノイマンの1945年の First Draft of a Report on the EDVAC は、これを工学に落とし込みました。つまり、プログラムとデータを同じメモリに格納する ということです。当時、ENIAC のようなコンピュータは文字どおり配線を変えて「プログラム」していたため、この設計判断は異端でした。けれども、この一つの選択こそが、現代のコンピュータを汎用機にしています。あなたがこれまで使ってきた CPU は、すべて薄く仮装した UTM なのです。
Tape — the infinite ribbon, faked beautifully
Turing machine のテープは無限ですが、実際のコンピュータのメモリはそうではありません。そこで工学的に用意された解決策が メモリ階層 です：
- Registers (~32 × 64-bit on x86-64) — sub-nanosecond access
- L1 cache (~32 KB) — ~1 ns
- L2 cache (~1 MB) — ~3 ns
- L3 cache (~30 MB) — ~10 ns
- DRAM (8–128 GB) — ~100 ns
- NVMe SSD (1–8 TB) — ~100 µs
- Network / cloud storage — milliseconds to seconds, effectively boundless
各層は、おおむね一つ上の層より10倍大きく、10倍遅いです。「無限テープ」の幻は、実用的なプログラムが比較的小さな作業集合を扱い、それが階層の上位に収まること、そして必要に応じてより大きなバックिंगストアをページインすることで保たれています。
Head — random access, not sliding
Turing machine のヘッドは1セルずつしか動きません。セル N に到達するには N ステップかかります。CPU はアドレスをバスに送り、メモリサブシステムは（おおむね）定数時間でそのバイトを返します。
これは能力の向上ではなく、速度の向上です。 Turing machine でも、1セルずつ移動すればランダムアクセスをシミュレートできます。ただ、時間がかかるだけです。両者は計算能力の点で等価ですが、プログラミングのしやすさは圧倒的に違います。私たちが何気なくポインタと呼ぶ「アドレス」は、単に「ヘッドがいるべき場所」を二進数で表したものにすぎません。
State — split into macro and micro
Turing machine の「状態」は、q_7 のような単一ラベルです。一方 CPU には、実質的に2層の状態があります：
- マクロ状態 — プログラムカウンタとレジスタの内容です。プログラマが意識するのはこれです。ヘッドの「論理的位置」と制御器の現在の規則にあたります。
- マイクロ状態 — パイプライン段、分岐予測器のエントリ、キャッシュラインの MESI 状態、リオーダーバッファの内容、投機実行の先端です。これらは抽象的な Turing machine には存在しません。1秒あたりにより多くの仕事を引き出すための工学的装置です。
Importantly: micro state is invisible to correct programs. The whole architectural discipline of “as-if serial semantics” means that, however wild the speculation and reordering, the result you observe is as if the CPU executed your instructions one at a time. The micro state is a performance optimization that preserves the macro abstraction.
（Spectre と Meltdown は、まさにこの不可視性の破れでした――マイクロ状態が観測可能なチャネルへ漏れ出したのです。）
Transition function δ — the instruction cycle
Turing machine の δ は、現在の状態と現在の記号が与えられたら、記号を書き、ヘッドを動かし、状態を切り替える と述べます。CPU も同じことをしていますが、粒度がずっと粗いだけです：
- Fetch — PC にある命令をメモリから読む
- Decode — ビットパターンを制御信号へ変換する
- Execute — ALU / load / store / branch の処理を実行する
- Writeback — レジスタを更新し、必要に応じて PC も更新する
x86 や ARM の各命令は、本質的には数十回分の Turing machine 風の遷移をまとめた マクロ です。x86 の MUL は1回の δ には収まりません。多くのより単純な δ からなるマイクロプログラムに展開され、しばしば microcode ROM に実装されます。命令セットは API であり、microcode は実装です。
だからこそ、CPU は意味のある形で UTM だと言えます。アーキテクチャ上の状態機械（PC + レジスタ）が汎用制御器の役割を果たし、メモリ上のプログラムがシミュレートされる機械の遷移表の役割を果たすのです。
Part 4 — What the Turing Machine Doesn’t Account For
忠実な対応表には、盲点も示しておくべきです。実際のコンピュータのいくつかの特徴は、元の Turing machine には対応物がなく、それらが何をもたらすのかを知っておく必要があります。
Parallelism
現代のチップには多くのコアがあり、GPU には数千ものコアがあります。複数のテープと複数のヘッドを持つ multi-tape Turing machine は、1本テープの機械と計算能力の点で同等であることが証明されています。n 本のテープでできることは、1本テープでも、せいぜい多項式的な遅延で実現できます。したがって、並列性は計算可能性を増やすのではなく、速度を上げるだけです。重要なのは、マルチコアでほぼ線形の高速化が得られる問題もあれば、まったく役に立たない問題もある、ということです。理論はこの違いを予測していました。
Pipelining and out-of-order execution
これらは遷移関数に対するスケジューリング上の工夫です。依存関係グラフが許すときに、複数の δ ステップを同時に適用しているにすぎません。抽象の下位にある話であり、プログラマの視点から見れば意味論は変わりません。
Interrupts and I/O
元の Turing machine には「外界」という概念がありません。停止するまで閉じたループで動き続けます。実際の CPU は interrupts を受け取ります。これは、実行をハンドラへ引き込む非同期の外部イベントです。これはモデルの本当の拡張であり、オペレーティングシステムが存在する理由でもあります。interrupts がなければ、CPU は1つのプログラムを完了するまでしか動けません。あるからこそ、複数の処理を切り替え、キーボードに応答し、ネットワークパケットを処理できる――要するに役に立つのです。
Virtual memory
MMU は 物理テープの上に仮想テープを実装 します。各プロセスは自分専用のアドレス空間（自分だけの「テープ」）を見ますが、物理メモリは共有されています。これは OS が UTM のトリックをさらに1段上で使っているのです。UTM が他の機械をシミュレートするように、仮想メモリを持つカーネルは、各プロセスに別々のコンピュータをシミュレートします。
Caching and prefetching
これらは、ヘッドが次にどこへ行くかという予測です。Turing machine は予測せず、ただ δ に従うだけです。CPU はプログラムの行き先を推測して先読みし、参照局所性が報われることに賭けます。たいていはうまくいきます。だからこそ「cache に優しいコード」は、抽象モデルにはない、実際に測定可能な関心事なのです。
Part 5 — A Useful Mental Model
他に何も覚えなくても、次の図だけは覚えておいてください：
あなたの CPU は、高度に最適化された Universal Turing Machine です。
- メモリに格納されたプログラムは、別の Turing machine の記述です。
- CPU ハードウェアは、その記述を走らせる汎用シミュレータです。
- OS は CPU 上の UTM の上で動く UTM であり、プロセスごとに1つの Turing machine をシミュレートします。
- 各コンテナや VM は、さらに別の UTM-on-UTM 層です。
ソフトウェアを起動するたびに、入れ子になった汎用機械のスタックに向かって、「この別の機械をシミュレートしてください」 と頼んでいるのです。それが、シリコンの奥底まで文字どおり起きていることです。この抽象が入れ子になるのは、Turing の「機械はデータとして符号化できる」という原初の洞察が、そのままきれいに合成できるからです。
Closing thought
Turing machine はしばしば「単なる理論モデル」と片付けられます。しかし、そうではありません。これは、これまでに作られたあらゆる汎用コンピュータの 組織原理 です。テープは RAM、ヘッドはアドレスバス、状態は microcode、遷移は ISA です。そして普遍性――つまり、機械が別の機械の記述を読み取り、それ自身になる能力――こそが、ソフトウェアをインストールできる理由なのです。
1936年の論文は、そのアーキテクチャを記述しました。1945年の EDVAC 報告書は、その工学的な形を名付けました。それ以降の90年は、その根本思想を変えることなく、より速く、より小さく、より壊れにくくするための実験だったのです。
そして時おり、この壮大な構造に硬い限界が最初から組み込まれているのだと思い出したくなったら、どこかのテープの上を小さなビーバーがまだ走り回っていて、不可能を見える形にしてくれます。
さらに読むなら
- Tibor Radó, On non-computable functions, Bell System Technical Journal, 1962.
- Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936.
- John von Neumann, First Draft of a Report on the EDVAC, 1945.
- The Busy Beaver Challenge (bbchallenge.org) — 2024年に Σ(5) を確定させた共同プロジェクト。
- Patterson & Hennessy, Computer Organization and Design — 対応関係がどのように工学化されるかを説明する標準的な教科書。