計算可能数について

原題は On Computable Numbers, with an Application to the Entscheidungsproblem。チューリングは23歳で、1936年5月に投稿し、Proceedings of the London Mathematical Society に掲載された。取り組んだのはヒルベルトの決定問題、つまり任意の数学的命題が公理から導けるかを判定する機械的手続きは存在するか、という問いである。答えるには、まず「機械的手続き」とは何かを定義する必要があり、彼は無限長のテープ、読み取りヘッド、状態遷移表を備えた架空の機械を記述することでそれを行った。

残りはすべてこの定義から導かれる。記述がテープ上に与えられれば任意の機械を模倣できる万能機械、任意の機械が停止するかを判定できる機械は存在しないという証明、そしてヒルベルトの問いへの否定的な答えである。アロンゾ・チャーチがラムダ計算で数か月早く同じ結論に達していたため、掲載が危ぶまれ、チューリングは両者の等価性を示す付録を加える羽目になった。この論文の真の遺産は証明そのものではなく、万能機械という脇道の発想、つまりプログラムがデータである機械にある。