讓機器跑起來：一個組態變成下一個組態
從第二篇起，你已握有所有零件：一條無限長的紙帶、一個落在某格上的讀寫頭、處於某狀態的有限控制器、一個含空白符號的帶字母表，以及一個轉移函數 delta——給定當前狀態與讀寫頭下的符號，它會說「寫下這個符號、向左或向右移動、並切換到這個狀態」。讓機器跑起來，無非就是把 delta 一次又一次地套用。要老實地想清楚「跑」會產出什麼，唯一的辦法是追蹤每一拍的整體情況——而那份快照有個名字：組態。
一個組態，捕捉了你若把機器凍結後、要恢復它所需的一切：當前狀態、整條帶子的內容，以及讀寫頭確切落在何處。人們把它精簡寫成帶子字串，再把狀態符號楔進讀寫頭下那一格之前，像是「a a q3 b b」。這讀作：帶子上是 a a b b，控制器處於狀態 q3，而讀寫頭正停在第一個 b 上。因為帶子兩側大多是空白，我們只寫出要緊的那段，其餘讓它保持空白。機器走一步，就把一個組態變成下一個——當你看著轉移函數動作時，那個「步進關係」正是它真正的意思。
三種結局，而非兩種
這裡有個真正全新的東西，是你在這座階梯上先前遇過的任何機器都沒有對應物的。一台 DFA 讀字串總會讀完——輸入用盡，你再看終止狀態是否為接受狀態。一台 NFA、一條正規表示式，甚至一台讀有限輸入的下推自動機，全都因其構造而必然終止。圖靈機卻不必。因為它既能向左也能向右移動、還能改寫格子，它可以永遠在帶子上遊蕩，從不抵達任何判決。所以一次對某輸入的計算，恰有三種可能的結局。
- 接受。機器進入它專屬的接受狀態。一進入的那一刻，它立即停機——這次執行結束，答案是「是，這個字串屬於我的語言」。此時帶子上是什麼、還剩多少輸入，都無所謂。
- 拒絕。機器進入它專屬的拒絕狀態。它同樣立刻停機——執行結束，答案是「否，這個字串不屬於我的語言」。接受與拒絕，是圖靈機停機的兩種方式。
- 永遠迴圈。機器從不進入任一個停機狀態。它一步接一步、無止境地持續套用轉移——也許在原地擺盪，也許一路向右行進、永遠寫著符號。它不給任何答案，因為它從不停止地「給」。這就是第三種結局：永遠迴圈。
對「迴圈」這個詞要當心。它不表示機器壞了，也不表示你寫了個糟糕的程式——迴圈是一台完全有效的機器、一個完全合法的結局。它也不表示機器當真一遍遍重複同一個組態；那是迴圈的一種方式，但機器也可以永遠運行卻從不重複，因為帶子是無限的，組態能不斷長大。「永遠迴圈」是對那唯一一個老實事實的簡稱：它從不停機。而關鍵在於：從外面看，無論你盯著看多久（任一段有限的時間），你一般都無從判斷一台仍在運行的機器，最終會停下、還是會永遠跑下去。記住這個念頭——它是兩階之後那個停機問題的種子。
識別對上判定：第三種結局逼出的那道裂縫
現在我們能精確地說，一台圖靈機「懂」哪個語言。圖靈機 M 的語言，是 M 所接受的所有字串構成的集合。請留意這定義裡烤進去的不對稱：一個字串屬於該語言，恰恰當 M 在接受狀態停機之時。但一個不屬於該語言的字串，卻能以兩種截然不同的方式失敗——M 可能拒絕它（一個乾淨的「否」），或 M 可能對它永遠迴圈（根本沒有答案）。就「判定是否屬於該語言」而言，從定義內部看，迴圈與拒絕長得一樣：兩者都不接受。但對你——那個守在機器旁等待的人——它們有天壤之別。
這正是為何理論家把一個直覺概念劈成兩個利落的概念。一個語言是圖靈可識別的，若有某台機器接受其中的每個字串——而對不在其中的字串，那台機器可以拒絕或永遠迴圈。識別器是一台對成員必定說「是」的機器，但對非成員，它可能讓你永恆地等下去、那聲「否」永不到來。一個語言是可判定的，若有某台機器接受其中每個字串且拒絕不在其中的每個字串，對每個輸入都必定停機。一台對任何輸入都會停機的機器，就是判定器；它是承諾絕不迴圈的識別器。每個可判定語言都可識別（判定器是附帶額外保證的識別器），但反過來不成立：有些語言可識別卻不可判定。圖靈可識別嚴格弱於可判定。
計算答案、而非只給是非的機器
目前為止，我們把機器當成一位說「是」或「否」的裁判。但圖靈機能做一件 DFA 或下推自動機從來辦不到的事：停機時，在帶子上留下一個有用的答案。如此使用時，機器就是一台轉換器——它計算一個函數。你把輸入放上帶子交給它，它停機（要算作「計算函數」，我們通常要求它停機），而帶子上剩下的任何字串就是輸出 f(輸入)。接受，只是其中一個特例：唯一要緊的輸出是單一個位元，是或否。這個更豐富的視角——機器作為函數的計算器——正是從「識別模式」通往「計算任何東西」的橋，而那便是邱奇–圖靈論題的去向。
讓我們用一個能想到的最謙卑的函數把它弄具體：把一個二進位數加一。設帶子上是 1 0 1 1（即二進位的 11），我們要機器停機時帶子上是 1 1 0 0（即 12）。加一無非就是課本上的「進位」，但由一台一次只看得見一格的機器來做，所以它必須來回挪動讀寫頭：先走到最低位那端，再一路爬回來、趁進位還活著時把位元翻轉。
Increment a binary number (head shuttles right, then back left)
Tape alphabet: 0, 1, _ (blank). Start at the LEFT end.
Phase 1 walk RIGHT to find the rightmost bit
keep moving right until you read a blank, then step left
Phase 2 add the carry from the low end, moving LEFT
on a 1 : write 0, keep the carry alive, move left
on a 0 : write 1, carry is absorbed -> HALT (done)
on _ : write 1, carry overflowed into a new digit -> HALT
Trace on input 1 0 1 1 (^ marks the head):
1 0 1 1 _ walk right ...
1 0 1 1 _
^ hit blank, step left onto last bit
1 0 1 1
^ read 1 -> write 0, carry, move left 1 0 1 0
^ read 1 -> write 0, carry, move left 1 0 0 0
^ read 0 -> write 1, carry absorbed 1 1 0 0 HALT
Result on tape: 1 1 0 0 = 12 . (11 + 1)設計一台真正的機器：用標記法做 a^n b^n c^n
現在讓我們在一個曾使先前模型束手無策的語言上活動筋骨。上下文無關語言的幫浦引理曾證明，{a^n b^n c^n : n >= 0}——等量的 a，接著等量的 b，再接著等量的 c——連上下文無關都不是：沒有下推自動機能識別它，因為單一堆疊能平衡兩個量、卻平衡不了三個。圖靈機卻能輕鬆應付，原因正是帶子是可讀也可寫的。訣竅是最重要的一項設計技巧：標記符號。每一輪劃掉一個 a、一個 b、一個 c，迴圈直到帶子用盡。
- 找出最左邊尚未標記的 a。把它換成一個標記（比方說 X）。若已沒有未標記的 a，那麼 a 這邊就完成了——向右掃過，檢查是否還剩下未標記的 b 或 c；若帶子全是標記，就接受，否則拒絕。
- 向右移到最左邊尚未標記的 b，並把它標記（比方說 Y）。若你抵達 c 區或一個空白卻沒找到未標記的 b，數量就無法相符——拒絕。
- 向右移到最左邊尚未標記的 c，並把它標記（比方說 Z）。若你衝出尾端卻沒找到未標記的 c，基於同樣理由，拒絕。
- 把讀寫頭一路挪回左邊、回到第一個未標記的符號，然後跳回步驟 1。每一趟恰好消去一個 a、一個 b、一個 c，所以這個迴圈跑 n 次，接著步驟 1 的檢查確認三個區塊等量且順序正確。
有兩件事要注意。第一，這台機器必定停機——每一趟至少標記一個符號，所以它不可能永遠迴圈，這意味著它是判定器，而 {a^n b^n c^n} 是可判定的，不僅僅是可識別。第二，同一套工具一再現身：用標記來記住「這一個我已經數過了」，以及把讀寫頭左右來回挪動，以比較相隔甚遠的符號。這些技巧的近親，是把帶子當成數條平行的軌道——把每一格想成裝著一個小元組，這樣你就能在資料之上塗寫記帳資訊、卻不毀掉資料。標記、軌道與挪頭，是每一個圖靈機設計的家常便飯，而本階梯最後一篇會把一台從頭追蹤到尾。