通用圖靈機

通用圖靈機（Universal Turing Machine，又稱UTM或Machine U）是一種圖靈機，由艾倫·圖靈在1936年發明。這種多用途單機器（計算機器）模型可以「運行」任何任意（但well-formed）指令序列（稱為 "quintuples"）。這模型被一些人例如Davis (2000) 認為是「存儲程序電腦」的原點。存儲程序電腦一詞由約翰·馮·諾伊曼使用在他的《電子計算裝置》（"Electronic Computing Instrument"）。這種電腦現在使用馮·諾伊曼的名字稱為馮·諾伊曼結構。^[1]

這機器作為計算模型現在稱為「通用圖靈機」。^[2]

介紹

每台圖靈機從它的字母表得到字元串計算一確定的固定偏可計算函數。從外觀上它的行為就像一台使用固定程式的電腦。儘管如此，我們可以把任何圖靈機的動作表格編碼到一條字元串。因此，我們可以建構出一台圖靈機，它期待的紙帶上記載有一條用以描述動作表格的字元串緊跟着一條用以描述輸入的字元串，從而計算那台被編碼的圖靈機所計算的。圖靈在1936年的文章中詳細描述如此的構思。

“	它可以表達成一台單一的特殊機器，這種型式的機器可以被塑造成去做到所有工作。事實上，它可以被塑造成如同任何其他機器的模型般工作。這種特殊機器或許可以被稱呼為通用機器。	”
——1947年的艾倫‧圖靈

存儲程序電腦

相關條目

參考文獻

1. Davis, The universal computer: the road from Leibniz to Turing (2017)
2. Arora and Barak, 2009, Theorem 1.9