「計算可能な数について」

問いは数学の側から来た。「ある命題が証明できるかどうかを、 機械的な手続きで判定できるか」というヒルベルトの問題である。

答えるには「機械的な手続き」を定義しなければならない。 チューリングが考えたのは、紙テープに記号を書き、消し、 一マス動く、それだけの装置だった。 規則の表を変えれば、どんな計算でもできる。

そのうえで、この装置でも判定できない問いがあることを示した。 たとえば「ある手続きが止まるかどうか」を すべての場合について判定する手続きは存在しない。

否定的な答えだったが、副産物のほうが大きかった。 規則の表そのものをテープに書けば、 どんな機械の真似もする一台が作れる。 いま目の前にある機械は、その一台である。