the existence of undecidable languages

Before we name a single hard problem, there is a beautiful piece of pure bookkeeping that already tells us trouble must exist. Imagine an infinite library where every book is a language (a set of strings) and a separate, much shorter catalogue lists every program that could ever be written. If the catalogue of programs is genuinely smaller than the shelf of languages, then by simple counting most languages have no program at all. This is exactly the situation: there are vastly more languages than there are machines to recognize them, so undecidable, indeed even unrecognizable, languages must exist.

Here is the precise idea. Every Turing machine (equivalently, every program) is a finite string of symbols, so the set of all machines can be listed one after another: machine number 1, machine number 2, and so on. A set that can be listed like this is called countable. But a language is a subset of Σ* (Sigma-star, the set of all strings), and the collection of ALL such subsets is the power set of Σ*. Cantor's diagonal argument shows that the power set of any infinite countable set is uncountable: it is too big to be listed. So we have countably many machines but uncountably many languages, and a bigger set cannot be covered by a smaller list.

The punchline is non-constructive but devastating. Without exhibiting any particular problem, we already know that most languages are decided by no machine, and most are not even recognized by any machine. Pure counting guarantees the existence of the hard cases; it just does not point at one. The halting problem and A_TM later give us concrete, named examples we can hold in our hands, but the counting argument tells us in advance that such examples were unavoidable all along.