Ref.: Happy Anniversary To Turing’s Paper « Gödel’s Lost Letter and P=NP
艾倫·圖靈, 計算機科學之父, 計算機之父, 在 1936 年 5 月 28 發表經典論文 On Computable Numbers, with an Application to the Entscheidungsproblem.
圖靈在他的重要論文《論可計算數及其在判定問題上的應用》（On Computable Numbers, with an Application to the Entscheidungsproblem）(1936年5月28日提交）里，對哥德爾1931年在證明和計算的限制的結果作了重新論述，他用現在叫做圖靈機的簡單形式裝置代替了哥德爾的以通用算術為基礎的形式語言。由於速度很慢，儘管沒有一台圖靈機會有實際用途，圖靈還是證明了這樣的機器有能力解決任何可想像的數學難題，如果這些難題是用一種演算法來表達。現今，圖靈機還是計算理論研究的中心課題。他繼續證明了判定問題（Entscheidungsproblem）是沒有答案的。他的證明首先展示了圖靈機的停機問題(halting problem)是沒有答案的，這是說不可能用一個演算法來決定一台指定的圖靈機是否會停機。儘管他的證明比阿隆佐·邱奇在λ演算方面相等的證明晚發表了幾個月，圖靈的著作是更易於理解和直觀的。 他的通用（圖靈）機的概念也是新穎的。這一通用機能夠完成任何其他機器所能做的任務。這篇論文還介紹了可定義數的概念。
沒必要多說什麼, 共襄盛舉就好.
沒有留言:
張貼留言