通用圖靈機（universal Turing machine）

我們至今遇過的每台圖靈機都是專用的小裝置：這台測 a^n b^n，那台把兩個數相加。每一台都像單一用途的家電，一台只會烤吐司的烤麵包機。現在想像有一台機器，它不為任何特定任務而造，反而是讀取任何其他機器的描述，然後表現得與那台機器一模一樣。它就是那種「依你遞給它的說明書，而變成烤麵包機、果汁機或收音機」的家電。這就是通用圖靈機（universal Turing machine）。

通用圖靈機 U 接收一台機器 M 連同輸入 w 的編碼為輸入，記作 <M, w>，並模擬 M 在 w 上的運行。在內部，U 在它的帶（們）上保留三樣東西：M 的轉移規則的一份副本（即「程式」）、M 的帶子當前內容，以及標記 M 當前狀態與讀寫頭位置的記號。要走 M 的一步，U 掃描規則以找出與 M 當前狀態及所讀符號相符的那一條，然後據此更新模擬的帶子、狀態與讀寫頭，如此反覆。若 M 會接受，U 就接受；若 M 會拒絕，U 就拒絕；若 M 永遠迴圈，U 也永遠迴圈。

這是計算機科學中影響最深遠的想法之一。通用機是儲存程式電腦的理論祖先：「一塊固定的硬體能執行任何程式，因為程式只是餵給通用直譯器的資料」這個現代洞見，正是通用性。它也是不可判定性核心那部自我參照引擎，因為通用機可以被命令去模擬一台機器在它自己描述上的運行。誠實的提醒是：通用性談的是 U 能做什麼，而非多快，模擬 M 讓 U 每一步都有額外開銷，所以 U 比 M 慢（不過就標準構造而言只慢一個不大的倍數）。而且 U 逃不過 M 的命運：若 M 在 w 上永不停機，U 也不會。