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