通用圖靈機

通用圖靈機，是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程式。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程式表，根據程式輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。

能夠模擬其它所有圖靈機的圖靈機叫做“通用圖靈機”(UTM, Universal Turing Machine)。
[font color=#000000]圖靈機[/font]的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：
在紙上寫上或擦除某個符號；
把注意力從紙的一個位置移動到另一個位置。
艾倫‧圖靈的“通用計算機器”("universal computing machine"，或者"universal machine", "machine U", "U")是由他(1936-1937)為他的多用途單機器（計算機器）模型命名，這模型可以“運行”任何任意（但well-formed）指令序列（稱為 "quintuples"）。這模型被一些人例如Davis (2000) 認為是“存儲程式電腦”的原點。存儲程式電腦一詞由約翰·馮·諾伊曼使用在他的《電子計算裝置》（"Electronic Computing Instrument"）。這種電腦現在使用馮紐曼的名字稱為馮·諾伊曼結構。
這機器作為計算模型現在稱為“通用圖靈機”。
[編輯] 介紹
每台圖靈機從它的字母表得到字元串計算一確定的固定偏可計算函式。從外觀上它的行為就像一台使用固定程式的電腦。儘管如此，我們可以把任何圖靈機的動作表格編碼到一條字元串。因此，我們可以建構出一台圖靈機，它期待的紙帶上記載有一條用以描述動作表格的字元串緊跟著一條用以描述輸入的字元串，從而計算那台被編碼的圖靈機所計算的。圖靈在1936年的文章中詳細描述如此的構思。
“ 它可以表達成一台單一的特殊機器，這種型式的機器可以被塑造成去做到所有工作。事實上，它可以被塑造成如同任何其他機器的模型般工作。這種特殊機器或許可以被稱呼為通用機器。 ”
──1947年的艾倫‧圖靈