從筆記本到七元組
上一篇裡，圖靈機是一幅畫面：一條永無盡頭的紙帶、一個停在某格上方的讀寫頭，外加一顆會讀取頭下方內容、寫回某個東西、再向左或向右挪一步的小小有限大腦。畫面是個好開頭，但要證明定理，我們得把這幅畫面毫無歧義地寫下來——每個部件命名、每條規則釘死。形式定義做的正是這件事，把整台機器塞進一個七元組：(Q, Sigma, Gamma, delta, q0, q_accept, q_reject)。它看起來比 DFA 的五元組沉重，但真正全新的只有兩塊，而且兩塊都來自同一個源頭——那本你現在可以寫字的筆記本。
其中三塊是老朋友。Q 是有限的狀態集合，也就是機器那顆小而固定的大腦。q0 是起始狀態。而圖靈機不用一整組接受狀態，乾脆只留兩個停機狀態：q_accept 與 q_reject，兩者必須相異。Sigma 是輸入字母表——你的輸入字串被允許使用的那些符號，跟有限自動機完全一樣。到此為止，這不過是穿了件略微不同外套的 DFA。真正的躍進在剩下的兩塊：一個更豐富的紙帶字母表，以及一個不只是改變狀態的轉移。
紙帶字母表與空白符
紙帶就是那本無界的筆記本：一條由格子組成、向右無限延伸的線（有些教科書讓它向兩邊延伸——這對機器能計算什麼毫無影響）。一開始，你的輸入字串安坐在最左邊的那些格子裡，其餘每一格都是空白。由於機器既能寫又能讀，它需要一些輸入裡從未出現過的符號可寫——擦痕、分隔符、用來算的 0 或 1。於是格子所取用的池子比 Sigma 大：那就是紙帶字母表 Gamma（大寫的 gamma）。
兩條規則把 Gamma 釘住。第一，Sigma 是 Gamma 的子集——每個輸入符號當然都是合法的紙帶符號。第二，Gamma 含有一個 Sigma「不可以」含有的特殊字元：空白符，通常畫成一個小方框（這裡寫成 'B'）。空白符填滿輸入沒觸及的每一格，也是機器感知資料到哪結束的方式：輸入右邊的第一個空白，標示著「再沒有給更多了」。把空白符排除在 Sigma 之外不是龜毛——正是它讓機器能可靠地把真正的輸入與空白草稿區分開來。
一步動作：先寫，再移
現在來到核心。DFA 的轉移讀一個字母、改變狀態——它能做的就只有這些。圖靈機的轉移函數 delta 在一個不可分割的動作裡做三件事，因為它操控的讀寫頭既能寫又能走。它的型別是 delta(q, X) = (p, Y, D)，用白話講：當機器處於狀態 q、讀寫頭正讀到符號 X 時，就移到狀態 p、把那一格覆寫成符號 Y、再把讀寫頭往方向 D 挪一格——D 不是 L（左）就是 R（右）。三項效果，時鐘的一聲滴答。
注意這條單一規則買到了多少。寫 Y = X 表示「這格別動」（純粹讀取後移動，就跟 DFA 一樣）。寫一個不同的 Y 則是真正的編輯——機器能留下一個麵包屑、劃掉一個已計數的符號，或一格一格地搭出答案。而由於讀寫頭可以往左走，機器能回到它已經經過的資料，這正是有限自動機永遠做不到的那件事。改寫加上回頭這個組合，就是圖靈機之所以能逃出困住 DFA 的有限記憶體天花板、以及困住 PDA 的單堆疊紀律的全部原因。有些教科書另外允許第三個方向 S（原地不動）；那是方便的簡寫、不增添任何能力，因為原地不動總能用「先右後左」假裝出來。
格局：一行寫盡整台機器
正如 PDA 有它的瞬間描述，圖靈機有一個格局（configuration）——一張完整的快照，你能寫在便利貼上以暫停運行、再原封不動地接續。要凍結一台圖靈機，你需要三項事實：它在哪個狀態、紙帶的確切內容、以及讀寫頭停在哪。那個巧妙的記法把三者摺進單一字串：寫下紙帶內容，但把當前狀態插在讀寫頭正在讀的那個符號「之前」。於是 1 0 1 q3 0 1 1 表示紙帶上放著 1011011、機器處於狀態 q3、而讀寫頭正坐在那個 0 上——也就是緊接在狀態名稱之後的那一格。
何必費事這樣打包？因為它把「機器在運行」變成字串之間一個乾淨的數學關係：一個格局依 delta「產生」下一個，正是移動關係 |- 對 PDA 所扮演的角色。起始格局是 q0 接著輸入、讀寫頭在第一個符號上；自此每一步覆寫一格、並把狀態標記往左或往右滑一格。一整段計算不過是一串格局、每個產生下一個，而對圖靈機進行推理，幾乎總是意味著推理這些快照如何演化。
delta rules (machine that just marks the first 'a' as 'X' then walks right to a blank): delta(q0, a) = (q1, X, R) in q0 reading a: write X, go right, enter q1 delta(q1, a) = (q1, a, R) in q1: skip over a's, keep going right delta(q1, B) = (q_accept, B, R) hit the first blank: accept Configuration trace on input a a (B = blank, head sits on symbol right after the state name): q0 a a B ... start: state q0, head on first a X q1 a B ... wrote X, stepped right, now in q1 X a q1 B ... skipped the a, stepped right, still q1 X a B q_accept ... read the blank -> accept; head one cell further right Read 'q0 a a' as: tape is 'aa', head on the a just after q0.
設計小機器，與標準技巧
握有定義之後，你就能搭出真正的機器。拿語言 a^n b^n c^n 來說——等量的一串 a、接著一串 b、再接著一串 c。眾所周知，下推自動機「無法」辨識它；一個堆疊能平衡兩群、卻平衡不了三群。圖靈機可以，而它的設計是核心技巧標記（marking）的生動一課：橫掃紙帶，每一趟劃掉一個 a、一個 b、一個 c（各覆寫成像 X 這樣的擦痕符號），再回到最左邊重複。若某一趟計數恰好對齊、只剩擦痕，就接受；若你曾經找不到相符的符號，就拒絕。那種來回——只因讀寫頭能往左走才辦得到——正是 PDA 永遠做不到的。
另外兩個標準技巧讓工具箱完整。多軌道：想像把每一格切成上下疊起的列，讓一格容納一個符號小元組——比如說 (資料, 標記)——使單一條紙帶能在上層軌道帶著一個數字、底下帶著一段持續更新的註記。這就是軌道的技巧，而它純粹是記帳：一條有 k 條軌道的紙帶仍是一台普通的單帶機器，只不過紙帶字母表是 k 元組罷了。還有穿梭：大多數圖靈機程式都是迴圈，把讀寫頭往右走去找某個特徵、做個小編輯、再往左走回某個標記——複製一個字串（讀一個符號、把它擺渡到一塊新區域）或把一個二進位數加一（走到低位端、把 1 翻成 0 直到撞上一個 0、把它翻成 1）實際上正是這樣運行的。
- 要把一個二進位數加一，先把讀寫頭一路穿梭到右邊、抵達最低有效位（標準的低位端）。
- 往左走，把讀到的每個 1 覆寫成 0——這些就是一路向上漣漪的進位——並繼續走。
- 一讀到 0（或越過高位端的一個空白）的那一刻，把它覆寫成 1 並停下：進位已落定。
- 那一趟帶覆寫的左掃就是二進位加一——一台四狀態機器，計算的是一個函數，而非只回答是/否。
最後那一點值得多想想。到目前為止，自動機永遠只回答是/否的成員資格問題，但一台停機時在紙帶上留下輸出的圖靈機，計算的是一個函數——它扮演著轉換器的角色，把一個輸入字串變成一個輸出字串。加一、複製、相加都是函數、不是語言，而同一條樸實的（寫, 移）規則就能全數搞定。辨識語言只是其中的特例：唯一在意的輸出只有「接受」和「拒絕」。下一篇會精確釘住這兩種裁決——並正面迎擊一個有限自動機從來沒有的、令人不安的第三種結局：那台根本不停下來的機器。