圖靈機（Turing machine）

想像一本無止盡的紙本筆記，整本只畫成一長排方格，再加上一位文書員：他一次只能讀一格、在格子上塗寫一個新符號、往左或往右挪一格，並隨時改變下一步要做什麼。這就是圖靈機（Turing machine）的全部構想。有限自動機像一個只記得自己處於哪個狀態的旋轉門；下推自動機多加了一疊只能從頂端碰的盤子。圖靈機則丟掉了這些限制：它的記憶體是一條無界的紙帶，能在任何位置、任意多次地既讀又寫。這一個改變，就足以讓它捕捉我們所說的「演算法」一詞的全部含意。

具體來說，圖靈機有兩個部分。有限控制就像 DFA 的腦袋：一個固定、有限的狀態集合，任一時刻只處於其中一個狀態。連著它的是一條被切成格子的無限紙帶，每格放一個符號，外加一個停在某格上方的讀寫頭。每一步，機器看自己當前的狀態以及讀寫頭正在讀的符號，轉移函數一次告訴它三件事：要往當前格寫入哪個符號（蓋掉原本的內容）、讀寫頭要往左還是往右挪一格、以及下一步要進入哪個狀態。它就這樣一步接一步地做下去。輸入字串一開始寫在紙帶上；其餘各處都放著一個特殊的空白符號。

圖靈機刻意被設計成最簡單、最笨、卻仍能計算任何可計算之物的小裝置。它很慢，只是把讀寫頭在紙帶上來回挪移，沒有人會這樣造一台真正的電腦。它的價值不在速度，而在精確：它對「一個問題能被某個演算法解決是什麼意思？」這個問題給出了單一、完全形式化的答案。數十年來用其他方式定義計算的嘗試（λ 演算、遞迴函數、暫存器機）最後都被證明捕捉到完全相同的可計算集合，這正是圖靈機成為可計算性標準定義的原因。