從定義到設計：在紙帶上思考
到了現在，圖靈機已不再陌生。你認得它是一本可讀、可擦、可重寫的無盡筆記本：一條向兩端無限延伸的方格紙帶、一個一次只停在一格上的讀寫頭，以及一個有限控制器——每一步看一眼頭下的符號，就觸發一條規則。前面幾篇把形式零件釘死了；設計一台機器則是相反的技藝。你不是讀規則再追蹤它們，而是從一個你想接受的語言、或一個你想計算的函式出發，自己發明那些規則。最有用的一個習慣是：在你寫下任何一條轉移之前，先決定每個狀態的意義——機器此刻正在「找什麼」。
一條轉移讀作 delta(q, a) = (p, b, D)：在狀態 q、看見符號 a 時，切換到狀態 p、把 a 改寫成 b，並把頭往方向 D（左 Left 或右 Right）移動一格。三件事同時發生——換狀態、寫入、移動——而正是這三連動讓轉移函式嚴格地比有限自動機更強。一台 DFA 只能換狀態；它永遠無法替未來的自己留下字條。圖靈機設計的全部本領，就是學會在紙帶上留下有用的字條，再走回去把它們讀出來。
標記訣竅：把紙帶符號當成劃掉的項目
圖靈機之所以能做下推自動機做不到的事，是因為它的工作字母表——即帶字母表（常寫成 Γ，gamma）——比輸入字母表更豐富。它包含輸入符號，加上那個填滿無限未用紙帶的特殊空白符號（常寫成一個小方框），再加上任何你想發明的額外記帳符號。那份自由正是最重要的設計技巧的核心：標記。為了記住你已經「用掉」某個符號，你只要把它改寫成一個帶標記的版本——把 a 改成 X、把 b 改成 Y——這樣等頭稍後來回經過它時，就知道那一格已經處理過了。
標記讓圖靈機變成一隻不靠任何有限狀態計數器就能計數與配對的生物。想想把購物清單上的項目劃掉：你不必記住一個數字，只要替每個項目打個勾。下推自動機可以靠它的堆疊用這種方式配對兩組東西——每個 a 推入、每個 b 彈出，這正是 a^n b^n 之所以是上下文無關的原因。但只要你需要同時配對三組，那一疊堆疊就不夠用了。圖靈機那條能被自由重掃的紙帶，沒有這種限制，而最經典的示範就是語言 a^n b^n c^n。
為 a^n b^n c^n 設計一台機器
在出現任何符號之前，先用白話講計畫。反覆地：找到最左邊未標記的 a 並劃掉它（寫 X），然後向右走到最左邊未標記的 b 並劃掉它（寫 Y），接著繼續走到最左邊未標記的 c 並劃掉它（寫 Z）；然後一路衝回最左端再來一次。每一趟完整的清掃，恰好按 a、b、c 這個順序各移除一個——所以它同時強制了數量相等以及正確的「先 a 後 b 再 c」順序。當你去找 a 卻發現一個也不剩，就做最後一趟：若此刻一切都已劃掉，接受；若還剩任何 b 或 c，就拒絕，因為數量沒對齊。
States (their MEANING): q0 : at left end, find next unmarked a (or finish) q1 : scan right for the next unmarked b q2 : scan right for the next unmarked c q3 : rush back left to the start, then repeat q4 : final check - only X Y Z left? -> accept Key transitions delta(state, read) = (state, write, move): delta(q0, a) = (q1, X, R) cross off an a, go hunt a b delta(q1, b) = (q2, Y, R) cross off a b, go hunt a c delta(q2, c) = (q3, Z, L) cross off a c, turn around delta(q3, X) = (q0, X, R) hit the left block, restart sweep delta(q0, Y) = (q4, Y, R) no a left: begin final check (q1,q2 skip over already-marked X/Y/Z; q3 moves left over a/b/c/Y/Z) Trace on input a a b b c c (n = 2): q0> a a b b c c head on 1st a X q1> a b b c c wrote X, hunting b X a b q2> b c c wrote Y over 1st b, hunting c (X a Y b ...) ... after one full sweep: X a Y b Z c then rush left ... after second sweep: X X Y Y Z Z then final check -> ACCEPT
親手追蹤它一次，這台機器就活了過來。上面每一行都是一個組態——對「（當前狀態、整條紙帶內容、頭的位置）」的完整快照——而計算的一步，不過就是一個組態在單一規則下產出下一個。看那頭怎麼穿梭：向右依序標記 a、b、c，然後一路向左回家，一遍又一遍。那種來回，即穿梭模式，是第二項核心技巧。圖靈機沒有隨機存取；要把此處的一個符號與遠方的一個符號比較，它必須親身在兩者之間走動，沿途留下標記好讓自己重新找到位置。
留意一個誠實的微妙處：這台機器是一台判定器。對 {a, b, c} 上的每一個輸入，它最終都會在接受或拒絕狀態停機——它絕不會進入無限迴圈，因為每一趟清掃都嚴格減少未標記字母的數量，所以這過程必然終止。這正是讓該語言可判定、而不只是可辨識的原因。對你設計的任何機器，永遠要問：「這在所有輸入上都可被證明會停機嗎？」若是，你得到一台判定器；若它在某些輸入上可能繞圈，你就只有一台辨識器——而這個區別，正是上一篇所講「判定」與「僅僅辨識」之間的差異。
軌道與「頭即鉛筆」：再兩項技巧
第三項技巧是多軌道。它感覺像作弊，卻完全合法：假裝那條單一紙帶被分成兩條或三條彼此疊放的平行車道，做法是讓每個帶格容納一個由符號組成的小元組，而非單一符號。一格可能裝著一對 (a, 空白)；讀它時，機器同時看見兩條車道，也能同時寫兩條。這由術語帶即軌道所刻畫，正是一台機器能在輸入旁附帶一條「草稿車道」、卻不需要第二條實體紙帶的原因——更大的帶字母表（現在裝的是對或三元組）把多出來的結構吸收進去了。
軌道讓複製機器容易想像。要把字串 w 複製成 w#w，就沿著 w 行進，對每個符號在第二條軌道上留下一個記號，記著「我已複製到這裡」，然後穿梭到 # 之後的空白區把該符號接上去。二進位數的遞增類似但更俐落：走到最右邊那位，然後向左清掃，把一連串的 1 翻成 0，直到碰上第一個 0（把它翻成 1 並停下）或衝出左端（寫一個新的最高位 1）。這些小機器——複製、遞增——是圖靈機版的「hello world」，它們展示了機器不只會接受／拒絕。
最後這點開啟了第四個觀念：圖靈機根本不必是個是／否的裁判。它可以是一台轉換器，用來計算一個函式——把 x 餵到紙帶上，讓它跑，等它停機時讀取留在紙帶上的結果。這正是圖靈機計算那些可計算函式的意涵：加法、乘法、排序，凡是程式做得到的一切。遞增機器計算的是 f(x) = x + 1。接受一個語言，不過是「輸出」為單一位元（接受或拒絕）的特例。同時記住這兩幅圖像——辨識器與函式計算器——正是讓圖靈機能代表「任何一台電腦」的關鍵。
這把你留在何處，以及該帶上去什麼
現在你的工具箱裡有四項技巧，而幾乎每一個圖靈機設計都是它們的重新組合。標記符號，以便不靠數字計數器就能計數與配對。穿梭讀寫頭，以便跨距離比較或複製。用軌道在輸入旁攜帶草稿資料。並記得機器可以輸出一個值，不只是一個裁決。再加上「每個狀態寫一句白話」的紀律，並親手追蹤幾個組態，你就能為出奇繁複的語言與函式設計機器。
你結束這一階時，握著對整座階梯中最強大模型的、可動手操作的紮實掌握。你能陳述它的形式定義、用組態替它拍快照、講述它的三種可能命運——接受、拒絕，或永遠繞圈——把可判定 vs 可辨識這條界線拉直，而現在還真能造出會計數、會複製、會計算的機器。最重要的是帶走一個觀念：圖靈機意在當「任何電腦所能做之事」的誠實替身。那個承諾就是邱奇—圖靈論題，它是通往前方各階的門扉，在那裡你會問更鋒利的問題——哪些問題沒有任何機器能解，哪些它能解卻慢得不可能。