圖靈完備語言

背景

艾倫·圖靈

艾倫·麥席森·圖靈（Alan Mathison Turing，1912.6.23 - 1954.6.7），英國數學家、邏輯學家、密碼學家和英國首位計算機科學家，被譽為計算機科學和人工智慧之父。

他對計算機科學的發展有著很高的影響力，他用圖靈機提供了算法和計算概念的形式化，圖靈機可以被視為通用計算機的模型。他的圖靈測試對人工智慧的發展，作出了重要的、典型的、具挑戰性的和持久的貢獻。

圖靈機

在 1928 年第八屆國際數學家大會上，德國數學家希爾伯特（David Hilbert，1862 - 1943）提出了關於數學的三個精闢問題：

First, was mathematics complete ...（數學是完備的嗎？）
Second, was mathematics consistent ...（數學是一致的嗎？）
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.
如果一個函式的值可以通過某種純機械的過程找到，那么這個函式就可以有效地計算出來。

在作為特定計算模型的圖靈機上產生的可計算函式，就被稱為圖靈可計算函式。

圖靈完備性

如果一個計算系統可以計算每一個圖靈可計算函式，那么這個系統就是圖靈完備的；或者說，這個系統可以模擬通用圖靈機。

圖靈完備性也可以用來描述計算機語言的計算能力。

定義

具有圖靈完備性的計算機語言，就被稱為圖靈完備語言。絕大多數的程式語言，都是圖靈完備語言。這包括：

廣泛使用的所有通用語言：
過程式語言，如 FORTRAN、Pascal 等。
面向對象語言，如 Java、Python 等。
多範式語言，如 Ada、C++ 等。

使用不太常見範式的大多數語言：

圖靈完備語言

基本介紹

背景

艾倫·圖靈

圖靈機

可計算函式

圖靈完備性

定義

非圖靈完備語言

相關詞條

熱門詞條