And thirdly, was mathematics decidable ?(數學是可判定的嗎?)
希爾伯特的第三個問題又被稱為判定性問題(Entscheidungsproblem)。為了證否這個命題,1936 年,圖靈發表了一篇論文,題為《論可計算數,及其在判定性問題上的套用》(On Computable Numbers, with an Application to the Entscheidungsproblem)。在這篇論文裡,圖靈提出了一種假設的計算裝置,他稱之為 A-Machine(Automatic Machine,自動機器),這就是圖靈機。
可計算函式
1938 年,在美國普林斯頓大學攻讀博士學位的圖靈,發表了一篇博士論文,題為《基於序數的邏輯系統》(Systems of Logic Based on Ordinals)。在這篇論文裡,圖靈定義了可計算函式:
A function is effectively calculable if its values can be found by some purely mechanical process.