計數論證（counting argument）

計數論證是「不可判定語言必然存在」背後的引擎。直覺就跟家長在派對上用的一樣：如果小孩比椅子多，那無論怎麼安排座位，總有小孩得站著。這裡椅子是機器（程式），小孩是語言。我們證明語言嚴格地比機器多，所以總有些語言找不到任何機器。整個論證的力量來自比較兩個無窮集合的「大小」，用的是 Cantor 的基數概念。

第一步：機器是可數的。一台圖靈機由固定字母表上的一個有限字串來描述，而我們可以把所有有限字串先依長度、再依字典序排序，得到完整的清單：第 1 台、第 2 台、第 3 台……沒有任何一台被跳過，所以機器的集合恰好和自然數一樣大。第二步：語言是不可數的。{0,1} 上的一個語言不過是對每個字串說「是」或「否」，這等同於一條無窮二進位序列（字串在語言中記 1，否則記 0）。Cantor 的對角線論證證明：沒有任何清單能涵蓋所有無窮二進位序列——給定任何提議的清單，把第 n 條序列的第 n 個位元反轉，就造出一條與清單中每一條都不同的新序列。所以語言無法被列舉。

兩相比較：可數多台機器、不可數多個語言。可數清單能與自然數一一對應；不可數集合則不能。因此「機器對應到它所識別的語言」這個映射不可能是映成（onto）的：它整整漏掉了不可數多個語言。那些被漏掉的語言根本沒有任何機器能識別它們（不可識別），尤其也沒有任何機器能判定它們（不可判定）。論證很乾淨，但要記住它的極限：它是純粹的存在性證明，不會交給你任何一個具體的元兇。