1936年に発表された本論文は、「計算」の本質を数学的に定義した画期的な研究である。チューリングは、テープとヘッドを持つ単純な機械モデル（チューリングマシン）を考案し、「計算可能性」を厳密に定式化した。さらに、あらゆる機械の動作を模倣できる「万能計算機械」の存在を示し、これは現代コンピュータの理論的原型となった。また、このモデルを用いて原理的に解けない問題が存在することを証明し、ヒルベルトの「決定問題」を否定的に解決した。
On Computable Numbers, with an Application to the Entscheidungsproblem
すべてのコンピュータの原点：チューリングの1936年の論文は何を「発明」したのか
現代社会はコンピュータなしには成り立たない。スマートフォンからクラウドサーバーまで、我々の生活は計算機によって支えられている。しかし、そもそも「計算する機械」とは何だろうか。その理論的な設計図、そしてその能力の限界を初めて描き出したのが、アラン・チューリングが1936年に発表した論文「計算可能数、ならびにそのヒルベルトの決定問題への応用」である。本稿では、このコンピュータ科学の礎を築いた革命的な論文を紐解いていく。
1. 導入：電子計算機なき時代の思考実験
1936年、世界が再び大きな戦争へと向かう不穏な空気の中、この論文は発表された。この時代、「コンピュータ」という言葉は、計算作業を行う人間、特に多くの女性計算手を指す言葉であった。現代のような電子計算機は影も形もなく、計算は人間の頭脳、そろばん、あるいは歯車で動く機械式計算機に頼っていた。
物理的な機械が存在しない中で、チューリングは「計算」という行為そのものの本質を問うた。彼は、計算というプロセスを、物理的な制約から切り離された純粋な論理的プロセスとして捉え直すという、壮大な思考実験を行ったのである。
2. 著者と立場：数学の根源を問う若き天才
この論文を執筆したアラン・マシソン・チューリング は、当時ケンブリッジ大学キングス・カレッジのフェローであり、後にプリンストン大学の大学院に籍を置いた若き数学者・論理学者であった。彼はエンジニアでも経営者でもなく、純粋な理論研究者として、数学界の根源的な問題に取り組んでいた。
彼の直接の目的は、ドイツの偉大な数学者ダフィット・ヒルベルトが提示した「決定問題（Entscheidungsproblem）」を解決することであった。これは、「与えられた数学の命題が、正しいか間違っているかを機械的に判定する『一般的な手順』は存在するか？」という問いであり、当時の数学の基礎を揺るがす大問題であった。この問題に挑む中で、彼は「計算」そのものを定義する必要に迫られたのである。
3. 論文の概要：万能機械と計算の限界
この論文が提案・発見したものは、単なる一つの技術ではなく、計算機科学という学問分野そのものの基礎である。
「計算可能性」の定義: チューリングは、直感的でしかなかった「計算可能」という概念を、「ある機械によって実行できる」と厳密に定義した。
チューリングマシンの発明: その定義のために、彼は思考上の機械、後に「チューリングマシン」と呼ばれるモデルを考案した。これは、無限に長いテープ、テープ上の記号を読み書きするヘッド、そして機械の内部状態（有限個）から構成される、極めてシンプルな機械である。機械の動作は、「現在の状態」と「ヘッドが読んだ記号」の組み合わせだけで決まる一連の単純なルールに従う。
万能チューリングマシンの構想: さらにチューリングは、個別の計算しかできない専用マシンとは別に、あらゆるチューリングマシンの動作を模倣（シミュレート）できる「万能計算機械 (Universal Computing Machine)」の存在を理論的に示した。この万能マシンは、テープに書かれた他のマシンの「設計図（標準記述）」をプログラムとして読み込み、そのマシンになりきって計算を実行する。
計算の限界の証明: このモデルを用いて、チューリングは「原理的に計算不可能な問題」が存在することを証明した。その代表が「停止性問題」である。これは、「与えられたプログラム（チューリングマシン）が、特定の入力に対して計算を終えて停止するのか、それとも無限に動き続けるのかを判定する一般的なアルゴリズムは存在しない」というものである。この証明により、彼は決定問題を否定的に解決した。
4. なぜエポックメイキングだったのか
この論文が革命的であった理由は、それが「計算」の概念を物理世界から切り離し、純粋な数学的・論理的対象へと昇華させた点にある。
既存の考え方との違い: それまで「計算」は人間の知的活動や、特定の歯車の動きと結びついていた。チューリングは、その本質が「有限のルールに基づく記号操作」に過ぎないことを明らかにした。これにより、計算というプロセスそのものが数学的な分析の対象となり、後の計算理論の発展の道を開いた。
後世への影響:
- ジョン・フォン・ノイマン: 現代のコンピュータアーキテクチャの基礎を築いたフォン・ノイマンは、EDVACなどの初期コンピュータを設計する上で、チューリングの「プログラムをデータとしてメモリに格納する」という万能マシンのアイデアに大きな影響を受けたとされている。
- 計算機科学の誕生: 「計算とは何か」「計算能力の限界はどこにあるのか」という問いは、この論文によって初めて明確な形で定式化された。アルゴリズム、計算量、計算可能性といった計算機科学の根幹をなす概念はすべて、この論文に源流を持つ。
- 人工知能（AI）: 人間の知能や思考を計算プロセスとして理解しようとするAI研究の哲学的・理論的基礎も、この論文によって築かれたと言える。
5. 現代とのつながり：すべてのコンピュータに宿るチューリングの魂
チューリングの思考実験上の機械は、80年以上経った今もなお、我々のデジタル社会の根幹に息づいている。
受け継がれている技術: 私たちが使うパソコン、スマートフォン、サーバーなど、プログラムを実行するあらゆる現代のコンピュータは、万能チューリングマシンの物理的な実装である。CPUがメモリから命令（プログラム）を読み込んで逐次実行するという「フォン・ノイマン型アーキテクチャ」は、チューリングが示した万能性のコンセプトそのものである。プログラミング言語とは、人間が理解しやすい形で計算手順を記述するためのものであり、コンパイラやインタプリタがそれを究極的にはチューリングマシンが実行可能な単純な命令列へと翻訳しているのだ。
今読んでも学べること:
- 計算の本質への理解: 高度なグラフィックスやAIの裏で動いている「計算」という行為が、いかにシンプルで普遍的なモデルに基づいているかを理解できる。これは、技術の本質を見抜く上で強力な視点となる。
- 「できないこと」を知る重要性: エンジニアとして、計算には原理的な限界があること（停止性問題など）を知ることは極めて重要である。「この処理が完了するかを判定する完璧なプログラム」を組もうとするような、無駄な努力を避けることができる。
- 抽象化の威力: 複雑で捉えどころのない現象（人間の計算活動）を、テープとヘッドと状態という単純なモデルに抽象化し、その本質的な性質を解き明かす。この論文は、科学的・工学的な問題解決における抽象化の力を示す、最高の教科書でもある。
アラン・チューリングの1936年の論文は、単なる古い学術文書ではない。それは、私たちが生きるデジタル時代の「創世記」であり、すべてのソフトウェアエンジニア、研究者が一度は立ち返るべき原点なのである。
論文要約
導入
本論文の中心的な主題は「計算可能数」、すなわち、その値を小数として有限的な手段によって書き出すことが可能な実数である。この概念は、整数変数や実数変数を扱う計算可能な関数、計算可能な述語などへも容易に拡張可能である。チューリングによる定義では、ある数が計算可能であるとは、その数の小数表現を「機械」が印字できることを意味する。
この計算可能数のクラスには、実代数的数、ベッセル関数の実零点、そして円周率 (π) やネイピア数 (e) といった重要な数学定数が含まれる。しかし、定義可能な全ての数が計算可能であるわけではない。また、計算可能数のクラスは非常に広大であるにもかかわらず、可算（数え上げ可能）であることが示される。
この研究は、ゲーデルの不完全性定理と類似した結論を導き出す。そしてその最も重要な応用として、ヒルベルトが提示した「決定問題（Entscheidungsproblem）」が原理的に解くことのできない問題であることを証明する。また、本論文で提示される「計算可能性」は、アロンゾ・チャーチが別途提唱した「実効的計算可能性」と等価であることにも触れられている。
§1. 計算機械 (Computing machines)
計算のプロセスを厳密に定義するため、人間の計算行為をモデル化した抽象的な機械を導入する。この機械は以下の要素から構成される。
- テープ: マス目に区切られた一次元のテープ。紙の役割を果たし、各マス目には記号を一つ書き込むことができる。
- ヘッド: テープ上の一つのマス目を「走査」し、記号を読み書きする装置。
- 有限の状態: 機械は有限個の内部状態（論文中では "m-configurations" と呼ぶ）を持つ。これは計算中の人間の「心の状態」に相当する。
機械の動作は、その瞬間の「内部状態」と「走査している記号」の組み合わせによって一意に決定される。機械が行える操作は、記号の書き込み、記号の消去、ヘッドの左右への移動、そして内部状態の変更のみである。チューリングは、これらの単純な操作の組み合わせが、人間が行ういかなる計算プロセスをも実行可能であると主張した。
§2. 定義 (Definitions)
§1で導入した機械の概念を基に、以下の用語を厳密に定義する。
- 自動機械 (Automatic machine / a-machine): 各段階の動作が、外部の介入なしに、その時点の構成（状態と記号）によって完全に決定される機械。
- 計算機械 (Computing machine): 数字である「0」と「1」（第一種の記号）と、計算の補助に用いるそれ以外の記号（第二種の記号）を印字する自動機械。
- 計算された数 (Computed number): 計算機械が空のテープから始動し、印字した第一種の記号の列の先頭に小数点を付けたもの。
- 非円状 (Circle-free): 第一種の記号（数字）を無限に印字し続ける機械。もし有限個しか印字しない場合は「円状 (circular)」である。
- 計算可能な数列・数 (Computable sequence/number): 非円状の機械によって計算できる数列を「計算可能数列」と定義する。
§3. 計算機械の例 (Examples of computing machines)
具体的な計算機械の動作を理解するため、2つの例が示される。動作は「状態遷移表」を用いて記述される。
- 例 I:
010101...という単純な繰り返し数列を計算する機械。4つの内部状態を持ち、記号「0」と「1」を交互に印字しながらテープ上を右に移動し続ける。 - 例 II:
0010110111...という、1の個数が一つずつ増えていく、より複雑な数列を計算する機械。この例では、計算結果の数字を書き込むマス (F-squares) と、計算途中のメモを記すための一時的なマス (E-squares) を交互に利用するという、後の議論で重要となるテクニックが導入される。
§4. 省略されたテーブル (Abbreviated tables)
機械の設計が複雑になると、状態遷移表の記述は長大になる。これを簡潔にするため、「スケルトンテーブル」という省略記法が導入される。これは、特定の処理パターン（例：「テープ上で左端にある特定の記号を見つける」）を一つのまとまり（m-function）として定義し、それを変数を含む形で記述するものである。これにより、機械の構造をよりモジュール化し、理解しやすくすることができる。
§5. 計算可能数列の数え上げ (Enumeration of computable sequences)
本章では、全ての計算可能数列が数え上げ可能（可算）であることが証明される。その証明は以下の手順で行われる。
- 標準形式への変換: 全ての計算機械の状態遷移表を、定められた単純な形式の命令のみから構成される「標準形式」に変換する。
- 標準記述 (Standard Description, S.D.): 標準形式のテーブルを、特定の文字（A, C, D, L, R, N, ;）のみを用いた一意の文字列に変換する。
- 記述番号 (Description Number, D.N.): 標準記述の各文字をさらに数字に置き換えることで、全ての計算機械を一つの自然数で表現する。
各計算機械が一つの自然数（記述番号）に対応するため、全ての計算機械の集合は自然数の集合と同じく可算である。そして、各計算可能数列は少なくとも一つの計算機械によって生成されるため、計算可能数列の全体もまた可算であることが結論付けられる。
§6. 万能計算機械 (The universal computing machine)
個別の計算を行う専用機械とは対照的に、あらゆる計算可能数列を計算できる単一の機械、すなわち「万能計算機械 (Universal Computing Machine)」の存在が示される。
この万能機械 U は、テープの冒頭に任意の計算機械 M の標準記述（S.D.）をプログラムとして与えられると、そのS.D.を解釈し、M の動作を完全にシミュレートする。つまり、万能機械は、他の機械の設計図を読み込んでその機械になりきる能力を持つ。これは、現代のコンピュータが様々なソフトウェアを実行する概念の理論的な先駆けである。
§7. 万能機械の詳細な記述 (Detailed description of the universal machine)
前章でその存在が示された万能機械 U について、その具体的な状態遷移表を省略記法（m-function）を多用して詳細に記述する。このテーブルは、テープに与えられたS.D.（プログラム）を解析し、シミュレート対象の機械の現在の状態をテープ上で管理し、S.D.の指示に従ってテープを更新し、状態を遷移させる、という一連の動作を実装したものである。
§8. 対角線論法の適用 (Application of the diagonal process)
計算可能数列が可算であることから、カントールの対角線論法を用いて「計算不可能な数」を構成できる。しかし、この章ではその議論をさらに一歩進め、計算の限界に関する重要な結論を導く。
中心的な結果は、「ある与えられた計算機械が非円状（circle-free）であるか、すなわち無限に数字を計算し続けるかを判定する一般的なアルゴリズム（計算機械）は存在しない」というものである。
この証明は背理法による。もしそのような判定機械 D が存在すると仮定する。すると、この D を利用して、全ての非円状機械を順番にリストアップし、n番目の機械のn番目の数字を並べて新しい数列β'を作る機械 H が構築できる。しかし、この機械 H 自身の記述番号を H に入力した場合を考えると、H が停止するなら停止せず、停止しないなら停止するという矛盾が生じる。したがって、最初の仮定（判定機械 D の存在）が誤りであったと結論される。これは「停止性問題」の解決不可能性の証明に他ならない。
§9. 計算可能数の範囲 (The extent of the computable numbers)
本論文で定義した「計算可能性」が、我々が直感的に「計算できる」と考える範囲と一致するかどうかを考察する。この主張（現在では「チャーチ＝チューリングのテーゼ」として知られる）は、形式的な証明が困難であるため、以下の3つの観点からその妥当性が論じられる。
- 直感への訴え: 人間の計算プロセスは、有限の「心の状態」、有限種類の記号、そして一次元の紙（テープ）上での局所的な操作に分解できるため、本論文の機械モデルは人間の計算能力を的確に捉えている。
- 異なる定義との等価性: ヒルベルトの関数計算学における論理式を用いて定義される数のクラスが、本論文の計算可能数のクラスと一致することを示す。
- 豊富な例: 実際に、代数的数やπ、eといった広範な数のクラスが計算可能であることを例として示すことで、この定義の包括性を示す。
§10. 計算可能である数の大きなクラスの例 (Examples of large classes of numbers which are computable)
計算可能性の概念を関数へと拡張し、計算可能な関数に関するいくつかの重要な性質を証明する。
- 計算可能な関数を用いて再帰的に定義される関数は、同様に計算可能である。
- 計算可能な係数を持つべき級数は、その収束域内部で計算可能な関数を定義し、その和も計算可能である。
- 計算可能な連続関数に対して、中間値の定理に相当する定理が成り立つ。
これらの定理の結果として、全ての実代数的数、ベッセル関数の実零点、そして π や e といった数が、本論文の定義の下で計算可能であることが数学的に示される。
§11. 決定問題への応用 (Application to the Entscheidungsproblem)
本論文のクライマックスであり、§8の結果を用いてヒルベルトの決定問題（Entscheidungsproblem）が否定的に解決される。決定問題とは、「与えられた任意の論理式が、その形式体系内で証明可能であるか否かを判定する一般的な手続きは存在するか？」という問いである。
チューリングは、以下の論法でこれを証明した。
- 任意の計算機械 M に対して、論理式 Un(M) を構築する。この式は「機械 M がいつか記号 '0' を印字する」という命題を表現する。
- 「Un(M) が証明可能である」ことと、「機械 M が実際に '0' を印字する」ことが同値であることを示す（補題1、補題2）。
- もし決定問題が解決可能、すなわち任意の論理式の証明可能性を判定する一般的なアルゴリズムが存在したと仮定する。
- すると、そのアルゴリズムを使えば Un(M) の証明可能性も判定できるはずである。これは、機械 M が '0' を印字するか否かを判定できることを意味する。
- しかし、これは§8で証明された「ある機械が特定の記号を印字するかを判定する一般的なアルゴリズムは存在しない」という結論と矛盾する。
したがって、最初の仮定（決定問題が解決可能であること）が誤りであり、決定問題を解く一般的なアルゴリズムは存在しないことが結論付けられる。
付録 (Appendix): 計算可能性と実効的計算可能性
本論文でチューリングが導入した「計算可能性 (computability)」と、アロンゾ・チャーチがラムダ計算を用いて独立に定義した「実効的計算可能性 (effective calculability)」という、二つの異なる計算モデルが実は等価であることを証明する概要が示されている。
- λ-definable ⇒ Computable: ラムダ計算の式を評価・変換するプロセスをシミュレートする計算機械を構築することで、全てのλ-definableな数列が計算可能であることを示す。
- Computable ⇒ λ-definable: 計算機械の状態遷移やテープ操作を表現するラムダ式の体系を構築することで、全ての計算可能な数列がλ-definableであることを示す。
この等価性の証明は、計算とは何かという問いに対する異なる二つのアプローチが、同じ一つの根本的な概念を捉えていたことを示唆するものであり、「チャーチ＝チューリングのテーゼ」の強力な根拠となっている。
