圖靈完備性

關於該術語在預言機的相對可計算性理論中的用法，請見「圖靈歸約」。

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

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

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

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

非數學應用

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

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

正式定義

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

圖靈完全

一個計算系統可以計算任何圖靈-可計算函數，被稱作圖靈完全（或者圖靈完備）。或者任何可以模擬通用圖靈機的系統。

圖靈等價

如果一個計算系統可以計算的所有函數都是圖靈可計算的，則稱他為圖靈等價系統。這個系統可以計算的函數和通用圖靈機可以計算的是同一類，或者這個系統可以模擬通用圖靈機並被模擬。（所有已知的圖靈完備系統都是圖靈等價的，這為邱奇-圖靈論題提供了支援。）

（計算）通用性

如果一個系統可以計算一個類別的其他系統可以計算的每個函數（或可以模擬這個類別的每個系統），則該系統相對於這類系統稱為通用系統。 通常，通用性這一術語是針對圖靈完備類的系統預設使用的。 術語「弱通用性」有時用於區分僅通過修改圖靈機的標準定義才能實現其通用性的系統（例如細胞自動機）。

可計算性理論

主條目：可計算性理論

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

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

這種不可能性給分析真實世界的電腦程式帶來了問題。例如，沒人可以編寫一種工具，來防止程式設計師寫出無窮迴圈，或者防止用戶提供使程式無窮迴圈的輸入。

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

預言機

主條目：預言機

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

數字物理學

主條目：邱奇-圖靈論題

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

非圖靈完備語言

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

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

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

數據語言

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

參見

• 克萊尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯納–羅賓遜定理
• 跳躍逆轉定理
• 演算法資訊論
• 喬姆斯基譜系
• 邱奇－圖靈論題
• 可計算性理論
• 控制流程
• 判定器
• 萊斯定理
• 結構化程式理論
• 圖靈焦油坑

相關閱讀

• Brainerd, W. S.; Landweber, L. H. Theory of Computation. Wiley. 1974. ISBN 0-471-09585-0. 
• Giles, Jim. Simplest 'universal computer' wins student $25,000. New Scientist. 24 October 2007 [2020-07-04]. （原始內容存檔於2015-05-31）. 
• Herken, Rolf (編). The Universal Turing Machine: A Half-Century Survey. Springer Verlag. 1995. ISBN 3-211-82637-8. 
• Turing, A. M. On Computable Numbers, with an Application to the Entscheidungsproblem (PDF). Proceedings of the London Mathematical Society. 2. 1936, 42: 230–265 [2020-07-04]. doi:10.1112/plms/s2-42.1.230. （原始內容存檔 (PDF)於2020-11-30）. 
• Turing, A. M. On Computable Numbers, with an Application to the Entscheidungsproblem: A correction. Proceedings of the London Mathematical Society. 2. 1938, 43: 544–546. doi:10.1112/plms/s2-43.6.544. 

外部連結

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