兩種無窮，以及一場短缺
你在整道階梯上一直在做的事，就是替問題配上機器。正規語言配到一台 DFA，那個只記得當前狀態的旋轉閘門；上下文無關語言配到一台帶著一疊盤子（堆疊）的下推自動機；而在階層的最頂端，圖靈機——那本可讀、可擦、可重寫的無盡筆記本——能辨識的就多得多。於是人們很容易假設：機器總能往上擴張，迎合我們丟給它的任何語言。這一篇在我們還沒看任何具體問題之前，就先拆掉這個假設。真相很直白：語言遠遠多於機器，所以大多數語言根本配不到任何機器。
當兩邊都是無窮時要精確地說「更多」，我們需要你在數學工具那一階遇過的區分：可數與不可數。一個集合是可數的，若你能把它的成員排成一條單一的無窮清單——第一個、第二個、第三個，依此類推——使得每個成員都出現在某處，帶著一個有限的位置編號。自然數就是樣板。一個集合是不可數的，若沒有任何這樣的清單能裝下一切：你寫下的任何清單，都必然漏掉某些成員。兩種無窮大小之間的這道落差，正是這整個論證的引擎。
機器只有可數那麼多
先看供給面：圖靈機到底有多少台？每一台圖靈機都是一個有限的物件——一個有限的狀態集、一個有限的紙帶字母表，以及一張把每種組合都寫清楚的有限轉移表 delta，逐一列出 delta(q, a) = (p, b, 移動)。任何有限的東西都能被寫成一條有限的符號字串。所以每台機器都有一份有限的描述，一個編碼，我們通常寫成尖括號裡的字串 angle-bracket M angle-bracket。就計數而言，那台機器就是那條有限字串。
現在是關鍵的一步。固定任意一個有限字母表——比方說你用來寫編碼的那些符號。在有限字母表上的所有有限字串所成的集合，也就是你從基礎那一階就認得的 Sigma star，是可數的。你可以按長度把每條有限字串列出來：先是所有長度 0 的字串（只有 epsilon），再是所有長度 1 的字串按字母序，再是所有長度 2 的字串，依此類推。每條有限字串都坐落在這份清單的某個有限位置。既然每台機器都是這樣一條有限字串（而且許多字串根本不是合法的機器描述），機器就構成一個可數集合的子集。可數集合的子集仍是可數的。所以：圖靈機只有可數那麼多。原則上你能把今後將會存在的每一台機器排成 M_1、M_2、M_3，一台也不漏。
語言有不可數那麼多
現在看需求面：語言有多少個？回想一個語言不過就是一個字串的集合——Sigma star 的任意子集。所以所有語言所成的整族，就是 Sigma star 的冪集，亦即它所有子集的集合。而大小就在這裡分了家。Sigma star 本身雖然可數，它的冪集卻是不可數的。即使只是一個可數無窮集合，也沒辦法把它的所有子集都列出來；語言會溢出你能寫下的任何清單。
這個證明，就是康托爾（Cantor）用來證明實數不可數的那一個，替語言重新包裝了一遍：對角線論證。為了導出矛盾，假設你能把所有語言列成 L_1、L_2、L_3，依此類推。也把 Sigma star 的字串列出來，成為 s_1、s_2、s_3。現在造一個叛逆的語言 D，對角線語言，做法是沿著想像中那張方格的對角線往下走，在每一個被選中的字串上跟每一個被列出的語言唱反調。配方是：對每個 i，恰好在 s_i 不在 L_i 中時，把字串 s_i 放進 D。依此構造，D 在字串 s_1 上和 L_1 不同、在 s_2 上和 L_2 不同、在 s_i 上和 L_i 不同——對每個 i，它都在第 i 個字串上跟第 i 個語言唱反調。所以 D 不可能等於任何 L_i。然而 D 是一個完完全全正當的語言。清單漏掉了它。沒有任何語言清單能是完整的，而那恰恰就是不可數的意思。
s_1 s_2 s_3 s_4 ... (the strings of Sigma*) L_1 [ IN ] out IN out flip cell (1,1): s_1 NOT in L_1 -> put s_1 IN D L_2 out [out] IN IN flip cell (2,2): s_2 IS in L_2 -> keep s_2 OUT of D L_3 IN out [ IN] out flip cell (3,3): s_3 IS in L_3 -> keep s_3 OUT of D L_4 out IN out [out] flip cell (4,4): s_4 NOT in L_4 -> put s_4 IN D . . . . ---------------------------------- D OUT OUT OUT IN ... (each entry is the OPPOSITE of the boxed diagonal cell) D differs from L_i at string s_i, for EVERY i ==> D is on no row ==> the list was incomplete.
計數逼出不可判定性
把兩半合起來，結論便無可迴避。語言是不可數的；機器是可數的。可數的供給蓋不住不可數的需求——你沒辦法把一個不可數集合的每個成員都配上一個可數集合的相異成員，正如你沒辦法把不可數多位賓客安排到可數張椅子上。所以必定存在某些語言，是任何圖靈機都辨識不了的。既然判定器尤其也是一台辨識器，那些語言當然也絕不是可判定的。這就是定理不可判定（事實上是不可辨識）的語言存在，由一個純粹的計數論證證得。
把它磨利一點，好感受它有多極端。有辨識器的語言，在一個不可數的整體裡只構成一個可數的子集。所以若你把「所有語言」想成一片浩瀚的海洋，可辨識的那些不過是海中可數的幾滴水珠，而可判定的那些又是那幾滴裡更少的一撮。就這兩種無窮的精確意義而言，幾乎每一個語言都是不可辨識的，更別說不可判定。我們造得出的機器是稀有的例外，而非常態。這整道階梯上那些熟悉、乖巧的語言，全都住在那一道薄薄的可辨識縫隙裡——這正是為何直到此刻它們都感覺像是全世界。
這扇門通往何處
到目前為止，計數論證對「究竟哪些問題是辦不到的」保持沉默。這一階其餘部分的震撼在於：那些辦不到的問題並不奇異——它們正是你巴不得能對普通程式碼回答的問題。旗艦就是停機問題：給定一台機器和一個輸入，這台機器最終會停機，還是會永遠繞圈？你將看到，這個單一、極其實用的問題是不可判定的——不是只是慢、不是只是對大輸入很難，而是任何演算法都不可能在一般情況下、對每個案例、保證停機地回答它。證明再次動用對角線論證，只是這回掉頭向內：一台機器去問關於它自己的事，然後故意反其道而行。
從停機問題出發，這份不可能會擴散開來。一個密切相關的語言，通用接受語言 A_TM——機器 M 是否接受輸入 w？——結果是可辨識但不可判定的，而我們還會釘出一個連辨識都辨識不了的語言（它的補集）。接著 Rice 定理一舉把這片殘局推廣開來：機器所辨識的那個語言的每一個非平凡性質，都是不可判定的。把這條界線讀仔細——它談的是程式所計算的那個語言，而非原始碼文字的每一個語法性質。一支程式會不會印出「hello」、兩支程式是否計算同一個函數、程式碼是否符合它的規格：全都不可判定。落到現實世界的代價很具體：不存在通用的停機檢查器、不存在完美的程式等價檢查器、不存在毫無瑕疵的找蟲工具。計數告訴我們不可能就在那裡；接下來的幾篇，會把具體而有用的問題拖到光下來。