発見
| パラメータ | 値 |
|---|---|
| 提出日 | 1936年5月28日 |
| 出版 | Proceedings of the London Mathematical Society、series 2、vol. 42、pp. 230-265（1937年） |
| 著者 | アラン・マシスン・チューリング（1912年6月23日 - 1954年6月7日） |
| 所属 | キングス・カレッジ、ケンブリッジ |
| 解決した問題 | 決定問題（Entscheidungsproblem、ヒルベルトが1928年に提起） |
| 独立した並行成果 | アロンゾ・チャーチのラムダ計算（1936年4月、プリンストン） |
| 論文ページ数 | 36ページ（＋3ページの訂正、1937年） |
| 導入された概念 | チューリングマシン、万能機械、停止問題、計算可能性 |
技術的解説
1. 形式的定義 — チューリングマシンは以下で構成される：(a) 有限アルファベットのシンボル（空白記号□を含む）が書かれたセルに分割された無限のテープ、(b) 現在のシンボルを読み、シンボルを書き、テープを1セル左または右に移動できる読み書きヘッド、(c) 有限集合Q = {q₁, q₂, ..., qₙ}の中の現在の状態を保持する状態レジスタ、(d) 各（状態、読み取りシンボル）の組に対して新しい状態、書き込むシンボル、移動方向を決定する遷移表 δ: Q × Σ → Q × Σ × {L, R}。
2. 万能機械 — チューリングは、特定のチューリングマシンU（万能機械）が他のあらゆるチューリングマシンMをシミュレートできることを示した。Mの遷移表をUのテープ上にエンコードするだけでよい。万能機械はこの記述を読み、ステップごとに実行する。この概念はまさにプログラム内蔵方式コンピュータの原理である：同一の機械があらゆるプログラムを実行する。
3. 停止問題 — チューリングは対角線論法（カントールに着想を得て）により、すべてのマシンMとすべての入力xに対して、MがxでHALT（停止）するかLOOP（無限ループ）するかを判定できるチューリングマシンは存在しないことを証明した。証明：そのような判定機械Hが存在すると仮定する。入力Mに対し、H(M, M)を実行し逆のことを行う機械D（Hが「停止」と言えばループし、「ループ」と言えば停止する）を構成する。D(D)は何をするか？矛盾。よってHは存在し得ない。
4. チャーチ＝チューリングの提唱 — チューリングとチャーチは独立に同じ結果に到達した：計算可能な関数はすべてチューリングマシンで計算できる。これは定理ではなく（形式的に証明不可能）、経験的提唱である。1936年以降に考案されたいかなる計算モデル（ラムダ計算、セルオートマトン、量子マシン）も、チューリングマシンが計算できない関数を計算していない。異なるのは計算時間のみである。
なぜ成功したか
背景：1928年にダヴィッド・ヒルベルトが決定問題を提起した――あらゆる数学命題の真偽を決定する機械的手続きは存在するか？ チューリングはまず「機械的手続き」とは何かを形式化する必要があった。彼の抽象機械――根本的に単純な構成（テープ、ヘッド、状態、テーブル）――はすべての有効な計算の本質を捉えている。モデルの単純さがその強みである：追加可能な拡張（複数テープ、ランダムアクセスメモリ、並列性）はすべて速度のみを変え、計算可能な関数のクラスは変えない。
否定的結果（決定不能性）は肯定的結果（計算可能性）と同様に根本的である。絶対的な境界を示す：特定の問題は、現在および将来のいかなる機械によっても数学的に解けないことが証明されている。この「不可能の証明」こそ、チューリングの論文を単なる技術的貢献ではなく、知識の根本的限界の発見にしている。
因果連鎖
ヒルベルトが決定問題を提起（1928年）→ ゲーデルが不完全性を証明（1931年）→ チャーチがラムダ計算を定義（1936年）→ チューリングが抽象機械を形式化し決定不能性を証明（1936年）→ チューリングがブレッチリー・パークでボンベによりエニグマを解読（1939-1945年）→ フォン・ノイマンがEDVACプログラム内蔵アーキテクチャを設計（1945年）→ 最初のコンピュータ（ENIAC 1945年、マンチェスター・ベイビー 1948年）→ チューリングが人工知能テストを提案（1950年）→ プログラミング言語（Fortran 1957年、LISP 1958年）→ NP完全性の計算複雑性理論（クック、1971年）
エピソード
チューリングの論文は出版されないところだった。1936年5月に提出した際、チャーチがラムダ計算を介してまさに同等の結果を発表した（1936年4月）ことを知った。ケンブリッジでの師M.H.A.ニューマン（博士論文の指導教官はプリンストンのアロンゾ・チャーチである）は、チューリングの機械モデル――具体的、機械的、視覚化可能――がチャーチの抽象的形式主義よりも根本的に直感的であるとして、出版を維持するよう説得した。ニューマンは正しかった：最初のコンピュータの構築に直接影響を与えたのはラムダ計算ではなく、チューリングマシンであった。
出典
2026年8月のファクトチェック監査で検証された参考文献 — 本記事の記述は
以下のページと照合されています。