圖靈完備性

在可計算性理論，如果一系列操作數據的規則（如指令集、編程語言、細胞自動機）可以用來模擬任何圖靈機，那麼它便符合圖靈完備（Turing-complete或computationally universal）。這意味着這個系統也可以識別其他數據處理規則集，圖靈完備性被用作表達這種數據處理規則集的一種屬性。如今，幾乎所有編程語言都是具有圖靈完備性的。這個詞以引入圖靈機概念的數學家艾倫·圖靈命名。

還有一個相關概念是圖靈等價 – 如果P可以模擬Q並且Q可以模擬P，則兩台計算機P和Q稱為等效計算機。邱奇－圖靈論題認為任何可以通過算法計算其值的函數都可以由圖靈機計算，因此，如果任何真實世界的計算機都可以模擬圖靈機，則其對圖靈機是圖靈等價的。通用圖靈機可用於模擬任何圖靈機，且可以擴展現實世界計算機的計算方面。^{[NB 1]}

如果某物是圖靈完備的，則它可以用於模擬某些圖靈完備的系統。例如，一個指令式編程具有條件表達式（例如，「 if」和「 goto」語句，或者「branch if zero」的指令；請參見單一指令計算機）並且具有更改任意指令的能力，那麼它便具備圖靈完備性。

需要注意的是，雖然任何物理系統都不可能進行無限的迭代展開，但如果忽略這項限制，絕大多數物理系統都符合圖靈完備性。

非數學應用

在口語用法中，術語「圖靈完備性」或「圖靈等價」用於表示任何現實世界通用計算機或計算機語言都可以近似模擬任何其他現實世界通用計算機的計算方面、用途的計算機或計算機語言。

到目前為止構建的現實計算機可以在功能上進行分析，就像單帶圖靈機（對應於它們的內存的「帶」）一樣；因此，相關的數學問題可以通過足夠抽象的運算來應用。但是，現實計算機的物理資源有限，因此它們僅是線性有界自動機。與之對應的，通用計算機被定義為具有圖靈完備的指令集，無限內存和無限可用時間的設備。

正式定義

在計算理論中，有幾個密切相關的術語用於描述系統的計算能力。（比如抽象機器或者程序語言。）

圖靈完全: 一個計算系統可以計算任何圖靈-可計算函數，被稱作圖靈完全（或者圖靈完備）。或者任何可以模擬通用圖靈機的系統。
圖靈等價: 如果一個計算系統可以計算的所有函數都是圖靈可計算的，則稱他為圖靈等價系統。這個系統可以計算的函數和通用圖靈機可以計算的是同一類，或者這個系統可以模擬通用圖靈機並被模擬。（所有已知的圖靈完備系統都是圖靈等價的，這為邱奇-圖靈論題提供了支持。）
（計算）通用性: 如果一個系統可以計算一個類別的其他系統可以計算的每個函數（或可以模擬這個類別的每個系統），則該系統相對於這類系統稱為通用系統。通常，通用性這一術語是針對圖靈完備類的系統默認使用的。術語「弱通用性」有時用於區分僅通過修改圖靈機的標準定義才能實現其通用性的系統（例如細胞自動機）。

歷史

可計算性理論

可計算性理論使用計算模型來分析問題，並確定它們是否可計算，以及在什麼情況下可計算。可計算性理論的第一個結果是：存在一類問題，使一個（圖靈完備）的系統在一個任意長的時間後進行什麼操作，不可能被預測到。

一個經典的例子是停機問題：創建一種算法來作為圖靈完備語言的程序的輸入，並給該程序提供一些數據，來確定程序處理輸入後會最終停止或永遠繼續下去。對於某些輸入，創建這樣的算法微不足道，但總體上來說創建這種算法是不可能的。對於程序最後輸出具有的任何特徵，無法確定這種特徵是否能保持。

這種不可能性給分析真實世界的計算機程序帶來了問題。例如，沒人可以編寫一種工具，來防止程序員寫出死循環，或者防止用戶提供使程序死循環的輸入。

相反，可以限制程序的運行時間（時限）或者限制流程控制語句的使用（例如，只提供迭代已知數組內部元素的循環）。然而另一種定理說明，存在能夠被圖靈完備語言解決的問題，卻不能被任何循環能力受限的語言（即保證程序最後都會停止的語言）解決，因此所有這樣的語言都是圖靈不完備的。例如，一種保證程序完整運行並停止的語言，不能通過該語言內的所有可計算函數，來計算對角論證法中的可計算函數。

預言機

具有預言磁帶的計算機可能比圖靈機更強大：例如，磁帶可能包含停機問題或其他一些圖靈不可計算問題的解決方案。甚至具有隨機預言機也是不可計算的（幾乎必然），因為只有可數的計算而無數的預言。因此，具有隨機預言機的計算機可以計算出圖靈機無法執行的操作。

數字物理學

所有已知的物理定律都具有可通過數字計算機上的一系列近似值計算的結果。一種稱為數字物理學的假設指出，這並非偶然，因為宇宙本身可以在通用圖靈機上計算。這意味着無法在物理上構建比通用圖靈機更強大的計算機。

例子

非圖靈完備語言

存在很多並不圖靈完備的語言，比如由正則表達式表示的正則語言，通過有限狀態機進行識別。下推自動機和上下文無關文法更強大，但仍不是圖靈完備的，他們一般用於在程序編譯的初期階段生成分析樹。其他示例包括嵌入在Direct3D和OpenGL擴展名中的像素着色器語言的某些早期版本。^{[來源請求]}

在如Charity和Epigram之類的總函數式編程語言中，所有功能都是總的，必須終止。 Charity使用類型系統和基於範疇論的控制流程，而Epigram使用依賴類型。 LOOP語言的設計使其僅計算原始遞歸函數。所有這些都計算總可計算函數的正確子集，因為總的總可計算函數集不可計算。同樣，由於這些語言的所有功能都是合計的，因此與圖靈機相比，用於遞歸可枚舉集合的算法無法用這些語言編寫。

儘管無類型λ演算是圖靈完備的，但簡單類型λ演算不是。

數據語言

XML，HTML，JSON，和YAML不符合圖靈完備性，因為他們通常用來表示結構化數據而不描述計算。這些語言有時被稱為標記語言，或更恰當地稱為「容器語言」或「數據描述語言」。

參見

注釋

^ A UTM cannot simulate non-computational aspects such as I/O.

參考文獻

外部連結

Turing Complete. wiki.c2.com. [2020-07-04]. （原始內容存檔於2016-10-07）.

[1] A UTM cannot simulate non-computational aspects such as I/O.

[NB 1]