チューリングマシンの全貌：計算可能性・停止問題・普遍性と現代計算機科学への影響
エバープレイ編集部はじめに
チューリングマシンは、1936年にアラン・チューリング（Alan Turing）が提案した計算モデルで、現代の計算理論・理論計算機科学の基礎を成す概念です。見かけは非常に単純な抽象機械ですが、「何が計算可能か」を形式的に扱うための強力な道具であり、チューリング概念を通じて可算性、停止問題、普遍性（ユニバーサルマシン）、計算複雑性など多くの重要な概念が定式化されました。本稿ではチューリングマシンを技術者・研究者向けに詳しく解説し、その応用や限界、現代の計算機との関係まで深掘りします。
歴史的背景と目的
20世紀初頭、数学者たちはヒルベルトらが提示した決定問題（Entscheidungsproblem）に取り組み、「任意の数学的命題の真偽を決定するアルゴリズムは存在するか？」という問いがありました。チューリングはこの問題に対して、計算の直感的概念を厳密化するために「機械的に操作される記号列」をモデル化し、計算可能性の限界を示しました（Alonzo Churchのラムダ計算による独立した結果と合わせて、Church–Turingの立場を形成）。
形式的定義
標準的な（決定性）チューリングマシンは、以下の要素からなる7組または6組で定義されます。一般的な7組表記を示します。
- Q：有限の状態集合（状態レジスタが取りうる値）
- Σ：入力アルファベット（空白記号を含まない）
- Γ：テープアルファベット（Σ ⊂ Γ、空白記号 ␣ ∈ Γ）
- δ：遷移関数（決定性） δ : Q × Γ → Q × Γ × {L, R}（左移／右移）
- q0 ∈ Q：初期状態
- q_accept, q_reject ∈ Q：受理・拒否の終状態（通常は互いに異なる）
- （ブランク記号） ␣ ∈ Γ：テープの未使用セルを表す特別記号
計算は無限に延びた一方向または双方向のテープ上で行われ、ヘッドは1つのセルを読み書きしてL（左）、R（右）に移動します。遷移関数δによって状態遷移、書き換え、ヘッド移動が決定され、q_acceptやq_rejectに到達すると計算は停止します。δが部分関数である場合（ある組で定義されない場合）には、その時点で停止（非受理）とみなされる扱いもあります。
動作の具体例（単純な例）
例として、単純な一進数（1の列）を1つ増やす（末尾に1を追加する）非常に簡単なチューリングマシンを考えます。入力が「111」（3）であれば出力は「1111」（4）になります。
- アイデア：テープの右端（最初の空白）を見つけて1を書く。
- 状態遷移（概念的）：
- q0（初期）：1を読んだら右へ移動してq0のまま、空白を読んだら1を書いてq_acceptへ。
この種の簡単な例でも、チューリングマシンの読み書き・移動・状態遷移という基本原理が分かります。
拡張と変種
チューリングマシンには多くの変種があり、理論的性質の研究に利用されます。
- 非決定性チューリングマシン（NDTM）：遷移が複数選べるモデル。NPクラスの定義に用いられる。
- マルチテープチューリングマシン：複数のテープとヘッドを持つ。単一テープに比べ効率が高いが計算可能性は同じ。
- 普遍チューリングマシン（Universal Turing Machine, UTM）：任意のチューリングマシンの記述（プログラム）と入力を受け取り、その機械をシミュレートする機械。現代でいう「汎用コンピュータ」の理論的原型。
- オラクル機械：ある言語に対する特別な問い（オラクル）を定数時間で解けると仮定した拡張モデル。相対化議論などに使われる。
普遍性の概念とその重要性
チューリングが示した決定論的かつ単純な機械であっても、別の任意のチューリングマシンを「エンコード」した上でその動作を模倣できることが重要です。これが普遍チューリングマシン（UTM）です。UTMの存在は「プログラムをデータとして扱える」ことを意味し、後の保存プログラム方式（von Neumannアーキテクチャ）と理論的につながっています。
計算可能性と停止問題（Halting Problem）
チューリングは停止問題の非可判定性（undecidability）を証明しました：任意のチューリングマシンMと入力wに対して、「Mはw上で停止するか？」を判定する汎用アルゴリズムは存在しない、というものです。証明は自己言及的な対角化／還元の手法を用い、もし停止判定器が存在すれば矛盾が生じることを示します。
停止問題は特定の再帰列（再帰的に列挙可能な集合）に関連し、受理される入力の集合は再帰的列挙（recursively enumerable, R.E.）だが必ずしも決定可能（recursive）ではない、という計算理論の基本的な区別を生じさせます。
計算複雑性との関係
チューリングマシンは計算時間・空間（time/space）という計測尺度を与え、計算複雑性理論を構築するための標準モデルとなります。主なポイントは次の通りです。
- P：決定性チューリングマシンで多項式時間で解ける問題群（実用的な効率の理想的モデル）
- NP：非決定性チューリングマシンで多項式時間で受理できる問題群。P vs NP はこのモデル上で定義される主要問題。
- PSPACE、EXP などのクラスもチューリングマシンで自然に定義される。
- モデルの違い（マルチテープ vs 単一テープ等）による時間の違いは多項式（通常は二乗程度まで）で補償されるため、複雑性理論ではチューリングマシン間の多くの変種は等価（多項式時間で相互シミュレート可能）と見なされる。
重要な定理と概念
- Church–Turing 論題：直感的に「機械的に計算可能な関数」はチューリング計算可能であるという主張（数理的厳密証明ではなく立場／仮説）。
- 停止問題の非可判定性：任意の機械と入力の組に対する停止判定アルゴリズムは存在しない。
- ライスの定理：言語の非自明な性質（言語が特定の性質を持つか否か）は一般に決定不能である。プログラムの「振る舞い」に関する多くの性質が判定不能になることを示す。
- Busy Beaver 関数：n状態のチューリングマシンが停止する場合の最大ステップ数（または最大書き込み数）を与える関数で、超急増し非再帰的（非計算可能）である（Radoによる定義）。
実用と限界：現代のコンピュータとの比較
チューリングマシンは理論モデルなので現実のCPUやOSと直接一致するわけではありませんが、重要な点で関連しています。
- 普遍チューリングマシンはプログラム可能性を示すため、一般的な計算機（汎用コンピュータ）の理論的基礎となる。
- 実装面ではチューリングマシンは効率や実メモリ構成を無視した抽象モデルであり、キャッシュ・並列性・入出力の現実的制約などは別に扱う必要がある。
- 停止問題などの理論的不可能性は、実際のソフトウェア検証にも影響を与える（完全な自動バグ検出器は存在しない、という意味の理論的根拠）。
普遍チューリングマシンの効率（シミュレーションオーバーヘッド）
あるチューリングマシンを別のチューリングマシンでシミュレートするときの時間オーバーヘッドは理論的に研究されています。一般に、マルチテープ機を単一テープ機でシミュレートすると多項式（しばしば二乗）時間のオーバーヘッドで済みます。複雑性理論では多項式オーバーヘッドなら「効率的」とみなされるため、さまざまなチューリングモデルは本質的に同じ計算複雑性階層を定義します。
チューリングマシンの教育的・概念的意義
チューリングマシンは以下のような教育的・概念的価値を持ちます。
- 計算とは何かを明確にするための最小限の抽象モデルとなる。
- 不可判定性や計算複雑性の直観を養うための基本ツール。
- プログラムとデータの同一視や普遍性といった概念を形式的に示す教材として有用。
まとめと今後の視点
チューリングマシンは単純だが強力な抽象モデルで、計算可能性・不可判定性・複雑性といった計算理論の基礎を形作っています。現代のコンピュータ科学、プログラミング言語理論、形式検証、暗号理論など多くの分野に影響を与え続けています。実用上の課題（並列性や実メモリ構成、入力出力の扱いなど）は別途工夫が必要ですが、理論的基盤としての価値は変わりません。
参考文献
- A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936/1937) — Turing Archive
- Stanford Encyclopedia of Philosophy — "Turing Machines"
- Stanford Encyclopedia of Philosophy — "Computability and Complexity"
- Halting problem — Wikipedia（概要・証明の解説）
- Busy Beaver — Wikipedia（Radoの定義と性質）
- Michael Sipser, "Introduction to the Theory of Computation"（参考教科書の概説・講義ノート）
投稿者プロフィール
