# On Computable Numbers, with an Application to the Entscheidungsproblem > [!abstract] 概要 > 「計算可能数」とは、その小数展開が有限の手段によって計算可能な実数として簡潔に記述できる。本論文の主たる対象は表向きは計算可能数であるが、整数変数や実数・計算可能変数の計算可能関数、計算可能述語などを定義し調査することも同様に容易である。しかし、それらに内在する根本的な問題はどの場合も同一であり、最も煩雑でない手法を伴うものとして私は計算可能数を明示的に扱うことにした。私は近いうちに計算可能数、関数などの相互関係について報告したいと考えている。これには計算可能数によって表現された実変数関数の理論の展開が含まれるであろう。私の定義によれば、ある数が計算可能であるとは、その小数が機械によって書き出され得ることと同値である。 ## 論文情報 - タイトル: On Computable Numbers, with an Application to the Entscheidungsproblem - 著者: [[Alan Turing]] (The Graduate College, Princeton University, New Jersey / King's College, Cambridge) - 媒体: *Proceedings of the London Mathematical Society*, Series 2, Vol. 42 (1936–37), pp. 230–265 (Received 28 May 1936, Read 12 November 1936) - 原本: `.raw/papers/Turing_Paper_1936.pdf` ## 概要 Alan Turing が「計算とは何か」を数学的に厳密に定式化するために**チューリングマシン**および**普遍チューリングマシン**を考案し、これを用いて David Hilbert が提起した数学基礎論の最重要未解決問題「決定問題（Entscheidungsproblem）」が原理的に解決不可能であることを証明した、計算機科学・情報科学の歴史における最大級の金字塔論文である。 ## 問題設定 David Hilbert が提唱した決定問題（Entscheidungsproblem）——すなわち、与えられた一階述語論理の任意の数学的命題が真であるか否かを有限ステップの機械的手続きによって判定できるかという問いに答えるためには、「有限の手続き（アルゴリズム）」や「計算可能性」を数学的に曖昧さなく定義する必要があった。 ## 提案手法 1. **計算機械（Computing Machines / a-machines）**: マス目（squares）に区切られた1次元の無限長テープ、テープ上を1マスずつ移動・読み書き可能なヘッド、および有限個の内部状態（m-configurations）から構成される抽象機械を定式化。人間の計算者（computer）が紙の上でメモを取りながら有限の状態遷移と記号認識に基づいて計算を進める過程を極限まで抽象化した。 2. **標準記述（Standard Description）と記述数（Description Number）**: 各マシンの状態遷移表（命令群）を有限記号列（Standard Description）として一意に符号化し、さらにそれを1つの整数（Description Number）として表す手法を導入した。 3. **普遍計算機械（Universal Computing Machine, U）**: 任意の計算機械 $M$ の標準記述（プログラム）をテープの冒頭に配置し、その入力データとともに与えることで、$M$ の動作をステップバイステップで完全にシミュレートする単一の機械 $U$ を設計した。これは「ソフトウェアによってハードウェアの機能を任意に変更できる」という現代の蓄積プログラム方式（ノイマン型コンピュータ）の直接の起源となった。 ## 決定不能性の証明と決定問題への応用 1. **円滑性（circle-free）の判定不可能性**: 計算可能実数の小数を無限に出力し続けるマシンを円滑（circle-free）、停止または停止状態に陥るマシンを循環的（circular）と呼ぶ。対角線論法を用いて、「与えられた任意の機械の記述数が circle-free であるかを判定する機械」を仮定すると自己言及の矛盾が生じることを証明した（実質的な**停止性問題**の決定不能性）。 2. **決定問題（Entscheidungsproblem）の解決**: 任意の機械 $M$ が特定の記号を印字するかどうかという命題を、一階述語論理の論理式へと翻訳。もし決定問題が解けるならば機械の印字・円滑性も判定できてしまうことになり、矛盾が生じる。これにより、一階述語論理の決定手続きは存在し得ないという決定的な否定的結論を導いた（Alonzo Church のラムダ計算による証明と独立かつ同等の成果）。 ## 新規性・意義 「計算可能」という直観的概念に機械的な定義（チャーチ＝チューリングのテーゼ）を与え、普遍計算機という汎用コンピュータの概念モデルを人類史上初めて創案した。また、数学・論理学における限界（決定不能性）を明確に示した点で不滅の功績を持つ。 ## 強み / 弱点・課題 - **強み**: 人間の認知限界（状態数の有限性、一度に識別できる記号数の有限性）に基づいた哲学的・物理的説得力の高さ。 - **弱点・課題**: 原論文では記号表記や遷移表が極めて厳密かつ煩雑（m-configuration やスケルトンテーブルの展開）であり、後年の Post による定式化（チューリング・ポストマシン）等によって教育的な簡素化が図られた。