圖靈等價

圖靈完全指在可計算性理論中，程式語言或任意其他的邏輯系統如具有等同於通用圖靈機的計算能力。換言之，此系統可與通用圖靈機互相模擬。這個詞源於引入圖靈機概念的數學家阿蘭·圖靈（Alan Turing）。

基本介紹

• 中文名：圖靈等價
• 定義：在可計算性理論中，程式語言或任意其他的邏輯系統如具有等同於通用圖靈機的計算能力

圖靈完全指在可計算性理論中，程式語言或任意其他的邏輯系統如具有等用於通用圖靈機的計算能力。換言之，此系統可與通用圖靈機互相模擬。這個詞源於引入圖靈機概念的數學家阿蘭·圖靈（Alan Turing）。

雖然實際機器會受到存儲能力的物理限制，圖靈完全性通常指具有無限存儲能力的通用物理機器或程式語言。