圖靈完備性
維基百科,自由的 encyclopedia
在可計算性理論,如果一系列操作數據的規則(如指令集、編程語言、細胞自動機)可以用來模擬任何圖靈機,那麼它便符合圖靈完備(Turing-complete或computationally universal)。這意味着這個系統也可以識別其他數據處理規則集,圖靈完備性被用作表達這種數據處理規則集的一種屬性。如今,幾乎所有編程語言都是具有圖靈完備性的。這個詞以引入圖靈機概念的數學家艾倫·圖靈命名。
![]() | 此條目可參照英語維基百科相應條目來擴充。 (2020年6月21日) |
還有一個相關概念是圖靈等價 – 如果P可以模擬Q並且Q可以模擬P,則兩台計算機P和Q稱為等效計算機。 邱奇-圖靈論題認為任何可以通過算法計算其值的函數都可以由圖靈機計算,因此,如果任何真實世界的計算機都可以模擬圖靈機,則其對圖靈機是圖靈等價的。 通用圖靈機可用於模擬任何圖靈機,且可以擴展現實世界計算機的計算方面。[NB 1]
如果某物是圖靈完備的,則它可以用於模擬某些圖靈完備的系統。例如,一個指令式編程具有條件表達式(例如,「 if」和「 goto」語句,或者「branch if zero」的指令;請參見單一指令計算機)並且具有更改任意指令的能力,那麼它便具備圖靈完備性。
需要注意的是,雖然任何物理系統都不可能進行無限的迭代展開,但如果忽略這項限制,絕大多數物理系統都符合圖靈完備性。