第三種結局改變了一切
在上一篇裡，你見到一台圖靈機對一個輸入能做的三件事：進入接受狀態、進入拒絕狀態，或永遠跑下去而從不停機。那第三種結局是全新的。一台 DFA 總會讀完輸入然後停下；一台 PDA 也許有幾個空堆疊的死路，但在有限輸入上仍不會永遠跑下去；可是一旦我們給了讀寫頭一條它能改寫的紙帶、以及一個無須掉出邊緣的讀寫頭，我們也就給了機器原地空轉到永遠的能力。本篇的一切都從這一個事實流出：停機，如今成了一件機器有可能辦不到的事。
所以我們得仔細區分「機器接受一個字串」究竟是什麼意思，相對於「機器拒絕它」。接受是一個正向、可觀察的事件：機器最終停在它的接受狀態，而你看得到它發生。拒絕則分裂成兩種很不一樣的情況。機器可能停在它的拒絕狀態——一個乾淨、可觀察的「不」。或者它可能根本不停機——而從外面看，一台已經跑了十億步的機器，和一台會永遠迴圈下去的機器，長得一模一樣。光靠盯著看，你分不出下一步是會帶來答案，還是你正在等一個永遠不會來的答案。
辨識：是很可靠，不卻可能永不到來
一台圖靈機 M 辨識一個語言 L，意思是：對每一個字串，M 接受它，當且僅當該字串屬於 L。把這句讀仔細。對一個確實在 L 中的字串，M 被要求停機並接受。對一個不在 L 中的字串，M 則被允許做任一種「對拒絕而言不完美、但仍算正確」的事：停機並拒絕，或永遠迴圈。一個語言是圖靈可辨識的（較舊的名字是遞迴可枚舉的），當且僅當存在某台機器辨識它。辨識器是個忠實的「是」偵測器，卻是個不可靠的「不」偵測器。
日常的圖像是：一個辨識器是你按下啟動的一場搜尋，它承諾在找到目標的那一刻搖鈴——卻不承諾在永遠找不到時告訴你。想像一個程式，給它一個數，它去搜尋某猜想的一個證明，找到就接受。若證明存在，它遲早找到並搖鈴。若證明不存在，它就一直搜下去，永遠地、無聲地。你必定學到「是」；你永遠拿不到一個明確的「不」。這道不對稱——保證的是、可能無聲的不——就是辨識的全部個性。
有個值得釘牢的微妙點：「可辨識」不等於「容易」或「小」——一如在 DFA 階梯時，正規並不等於「有限」。一個可辨識的語言可以龐大而錯綜；唯一的保證，是成員的成員資格遲早會現身。而一台圖靈機 M 的語言——記作 L(M)——依定義就是 M 所接受的字串的集合，把它停機並接受的字串收進來，並完全不理會那些讓它迴圈的字串。那些迴圈的字串不在 L(M) 中，可是機器從未這麼告訴過你。
判定：一台總會停下來的機器
現在要求更多。一台圖靈機是一個判定器，如果它對每一個輸入都會停機——它在任何字串上都絕不迴圈。一個語言是可判定的（舊名：遞迴的），當存在某個判定器辨識它：這台機器接受每個在 L 中的字串、拒絕每個不在 L 中的字串，而且至關重要地，總在有限時間內抵達那兩個裁決之一。判定把辨識器那個不可靠的「不」升級成可靠的。如今「是」與「不」兩者都會回來，對每一個輸入、都有保證。
halts & accepts halts & rejects loops forever x in L (a member) REQUIRED no no x not in L (non-member) no ok for BOTH ok ONLY for recognizer DECIDER = recognizer that NEVER loops -> every cell is a halt -------------------------------------------------------------------- decidable ==> recognizable (a decider is also a recognizer) recognizable =/=> decidable (recognizing is strictly weaker)
每個可判定的語言都是可辨識的，因為一台總會停機的機器，特別也就是一台恰好接受正確字串的機器——判定器不過是個守規矩的辨識器。而那個深刻又出人意料的事實——再往上幾階的停機問題會證明它——是反過來不成立：存在一些語言是可辨識卻不可判定的。對那些語言，你能造出一台對每個成員都搖鈴的機器，卻沒有任何機器能造得出來，使它總會停機並給出正確的是或否。辨識與判定之間的那道缺口，不是暫時的工程限制；它是這片數學地景裡一個永久的特徵。
從是/不到計算函數
判定器回答是/不的問題，但一台圖靈機能做的不只投票——因為它的紙帶既能讀又能寫，機器停機時留在紙帶上的內容可以是一個答案，而不只是一個裁決。這樣使用的機器是一個轉換器：它計算一個函數。一開始把輸入寫在紙帶上，運轉，當機器停機時，紙帶上剩下的字串就是輸出 f(輸入)。若機器對每個輸入都停機，它就計算一個全函數；它與判定的關聯是精確的——一個 L 的判定器，不過是一台計算「接受」或「拒絕」這個函數（即 L 的特徵函數）的轉換器。
這裡有個最小的誠實例子：一台把二進位數加一的機器。輸入是一個二進位字串，最低位在右端。機器把讀寫頭移到最右邊那一位，然後往左走，沿途把 1 變成 0（那些就是進位），直到遇上一個 0 或一個空白，把它變成 1 然後停機。追蹤 0 1 1（也就是 3）：最右邊的 1 -> 0（進位），下一個 1 -> 0（進位），接著那個 0 -> 1，停機，留下 1 0 0（也就是 4）。它總會停機，因為讀寫頭只往左移動有限步，所以加一是個全可計算函數。這正是你會在下一篇拿來造 a^n b^n c^n 與字串複製器的同一塊「來回移動並改寫」的肌肉。
有兩項主力技巧讓這些設計變得可管理，而且兩者都會不斷重現。標記指的是用一個自身的裝飾版本覆寫某個符號——把一個 `a` 變成紙帶字母表裡一個劃掉的 `a`——好讓讀寫頭不必動用額外狀態就能記住「這個我已經處理過了」。軌道（tracks）指的是把一條紙帶當成數條平行車道，做法是擴大紙帶字母表，使每一格暗中裝著一個元組，讓機器能在輸入旁邊保留一個計數器或一份副本。靠著標記、軌道，以及耐心的左右來回移動，出奇地少的機件，就能判定出奇地多的東西。
把它組起來：你如今掌握的邊界
退一步，看看判定／辨識這道區別替你買到了什麼。語言分裂成三個層層相套的區域。最內圈：可判定的語言，那裡有某台機器總會停機並給出正確答案——這是「一個電腦能解的問題」的誠實含義。圍著它們：可辨識的語言，那裡機器能確認成員，卻可能在非成員上迴圈。在那之外：根本沒有任何圖靈機能辨識的語言。那些著名的不可判定問題，住在可判定與可辨識之間的那個環裡；而真正無望的問題，則住在可辨識之外。
- 要證明一個語言可判定，就拿出一個判定器：一台機器，外加一個它對每個輸入都停機的清楚論證（某個嚴格遞減的量、一個界限化的搜尋、一張有限的表要填）。
- 要證明一個語言可辨識，就拿出一個辨識器：一台對每個成員都停機並接受的機器；你獲准讓它在非成員上迴圈，所以停機論證較弱。
- 記住包含關係：每個可判定語言都可辨識，但反之不然。「可辨識但不可判定」是個真實且有住戶的類別——它的第一位住戶，是停機問題的語言，很快就會登場。
- 千萬別把「永遠迴圈」和「慢」或「難」混為一談。一個可判定語言可以花上天文般久卻仍是可判定的；一個不可判定的語言不是慢，而是可被證明地超出任何總會停機的機器之外。
為什麼這一道區別承載了這麼多分量？因為它就是「演算法能做與不能做」之間的分界線，沒有別的。在邱奇–圖靈論題之下，「可被圖靈機判定」被當成「可被任何演算法所解」——所以當我們最終證明某個語言不可判定時，我們不是在說我們那台特定的機器太弱；我們是在說，沒有任何演算法、用任何語言、在任何我們知道怎麼造的硬體上，能夠帶著「保證會結束」去解它。把判定／辨識這條線清楚地放在心裡，正是讓後面那些不可能性結果，能作為它們真正的驚奇而落地的關鍵。