不可判定語言的存在性（existence of undecidable languages）

在我們指名任何一個難題之前，有一段優美的純粹「點數」就已經告訴我們麻煩必然存在。想像一座無窮的圖書館，每本書是一個語言（一個字串集合），另有一份短得多的目錄列出所有能被寫出來的程式。如果程式的目錄真的比語言的書架小，那麼單憑點數就知道大多數語言根本沒有對應的程式。情況正是如此：語言遠比能識別它們的機器多，所以不可判定的——甚至連不可識別的——語言必然存在。

精確的想法是這樣。每台圖靈機（等價地，每個程式）都是一個有限的符號字串，所以所有機器的集合可以一台接一台列出來：第 1 號機器、第 2 號機器，依此類推。能這樣列出的集合稱為可數。但一個語言是 Σ*（Sigma-star，所有字串的集合）的子集，而「所有這類子集」的集族就是 Σ* 的冪集。Cantor 的對角線論證表明：任何無窮可數集合的冪集都是不可數的——它大到無法被列舉。於是我們有可數多台機器，卻有不可數多個語言，而較小的清單無法覆蓋較大的集合。

結論是非構造性的，卻極具殺傷力。在不舉出任何特定問題的情況下，我們就已經知道大多數語言沒有任何機器能判定它，而且大多數連任何機器都無法識別。純粹的點數保證了難題的存在，只是沒有指出哪一個。停機問題與 A_TM 之後會給我們可以握在手裡的具體、有名字的例子，但計數論證事先就告訴我們：這類例子一開始就無可避免。