Turing completeness

圖靈等價 & 圖靈完備

• 參考來源

經常在講編程語言的書或文章裡面看到圖靈等價（Turing equivalence）和圖靈完備(Turing completeness)，但卻不知道這兩個詞的精確含義和區別。尤其是很多書或文章經常對這兩個詞進行混用，我就很疑惑這兩個詞是不是就是一個意思。我用Google搜索了一下，很遺憾的是中文結果基本沒用，只有一篇百度空間裡面轉載的一個外國人寫的文章，還是全英文的，簡單看了下感覺寫得不怎麼清楚，就查了下英文維基百科。言歸正傳，下面先看看維基百科的兩段話：

In computability theory, a system of data-manipulation rules (such as an instruction set, a programming language, or a cellular automaton) is said to beTuring complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle anycomputer.

翻譯過來就是：在可計算理論里，一個數據操作規則的系統（比如：指令集、編程語言、細胞自動機）被稱作圖靈完備或者通用計算的，當且僅當它可以被用來模擬單帶圖靈機。

In computability theory, there is a closely related concept known as Turing equivalence. Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P. Thus, a Turing-complete system is one that can simulate a Turing machine, but the term is most often used to mean Turing equivalent to a Turing machine.

翻譯過來就是：在可計算理論里，有一個很相關的概念叫圖靈等價。當計算機 P 和計算機 Q 是圖靈等價的，當P可以模擬Q而且Q也可以模擬P。因此，一個圖靈完備的系統可以模擬圖靈機，但是這個術語（即圖靈等價）常常被用來指與圖靈機等價。

然後我們再來看看在可計算理論中，這兩個詞的正式定義：

Turing completeness：A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.

翻譯過來就是：圖靈完備：一個可以計算所有圖靈機可計算的計算系統被稱為圖靈完備的。換句話說就是一個可以模擬通用圖靈機的系統。

Turing equivalence：A Turing-complete system is called Turing equivalent if every function it can compute is also Turing computable; i.e., it computes precisely the same class of functions as do Turing machines. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known Turing-complete systems are Turing equivalent, which adds support to the Church–Turing thesis.)

翻譯過來就是：圖靈等價：一個圖靈完備的系統被稱為圖靈等價的，如果任何它可以計算的函數也是圖靈可計算的。也就是它可計算的函數和圖靈機可計算的函數是完全相同的。換句話說，就是圖靈等價的系統就是能模擬通用圖靈機同時也能也被通用圖靈機模擬的系統。（所有已知的圖靈完備的系統都是圖靈等價的，這增加了對丘奇-圖靈論題的支持）

通過上面的分析，我們就可以清楚的知道這兩個詞的意思和關係了。圖靈等價有兩個意思，一個是指兩個計算系統在可計算性上計算能力相同；另一個，也是常用的一個就是指一個系統的計算能力與通用圖靈機計算能力相同（在可計算性的意義上）。而圖靈完備是指能夠模擬通用圖靈機的計算系統。而所有已知的圖靈完備的系統都是圖靈等價的，這也增加了對丘奇-圖靈論題的支持。因此，在現有的計算機系統（編程語言、指令集等）上，使用圖靈等價和圖靈完備是一個意思。