通用圖靈機

通用图灵机（Universal Turing Machine，又称UTM或Machine U）是一种图灵机，由艾伦·图灵在1936年发明。这种多用途單機器（計算機器）模型可以「運行」任何任意（但well-formed）指令序列（稱為 "quintuples"）。這模型被一些人例如Davis (2000) 認為是「存儲程序電腦」的原點。存儲程序電腦一詞由约翰·冯·诺伊曼使用在他的《電子計算裝置》（"Electronic Computing Instrument"）。這種電腦現在使用冯·诺伊曼的名字稱為冯·诺伊曼结构。

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

介紹

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

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