圖靈機設計（Turing-machine design）

設計圖靈機，像是用想像得到最原始的語言寫程式：你唯一的操作是讀當前格、寫一個符號、往左或往右挪一格、改變狀態。沒有變數、沒有附計數器的迴圈、除了紙帶本身以外沒有記憶體。所以這門手藝是把一個高層想法（「檢查 a、b、c 的個數相等」）化為讀寫頭來回的細緻舞步，邊走邊留記號。你通常把它畫成狀態圖，和 DFA 那種泡泡加箭頭的圖一樣，只是每個箭頭都標上讀／寫／移動。

有幾種技巧反覆出現。標記：用紙帶字母表裡的特殊符號覆寫一個符號（把 a 劃成 X），好記住你已經處理過它。穿梭：把讀寫頭一路向右走、做點事、再一路往左走回來、重複，這就是你配對相隔遙遠之符號的方法。軌道：用複合符號假裝這單一紙帶有好幾條平行的列，好讓你在資料旁邊保有一個計數器或一份副本。要識別 a^n b^n c^n，你每次由左到右掃一遍就標記一個 a、一個 b、一個 c，並在每個符號都恰好一起被標記完時接受；要識別 ww，你會標記並比對兩半；要做二進位遞增，你走到低位端、讓進位一路漣漪過去。

設計機器培養出一種直覺：演算法能做的任何事，這套微小的指令集也能做，只是很繁瑣。那份繁瑣正帶出兩個誠實的提醒。第一，處理非平凡任務的真實機器有許多狀態、完整寫出來很痛苦，這正是為什麼我們很快轉向更高層的描述，並相信它們能被編譯下去。第二，這種慢是內在的：把讀寫頭穿梭過紙帶以比對相隔遙遠的格子，可能花費輸入長度平方甚至更糟的時間，所以圖靈機是「什麼可計算」的定義，絕非快速計算它的食譜。