Two infinities, and a shortage
You have spent this whole ladder pairing problems with machines. A regular language got a DFA, a turnstile that only remembers its current state; a context-free language got a pushdown automaton with its stack of plates; and at the top of the hierarchy, the Turing machine — an endless notebook you can read, erase, and rewrite — recognized far more. So it is tempting to assume that machines simply scale up to meet whatever language we throw at them. This guide demolishes that assumption before we even look at a specific problem. The truth is blunt: there are vastly more languages than there are machines, so most languages can have no machine at all.
To say 'more' precisely when both sides are infinite, we need the distinction you met back in the math-tools rung: countable versus uncountable. A set is countable if you can line its members up in a single infinite list — first, second, third, and so on — so that every member appears somewhere with a finite position number. The natural numbers are the model. A set is uncountable if no such list can ever contain everything: any list you write down necessarily leaves members out. That gap between the two sizes of infinity is the entire engine of this argument.
There are only countably many machines
Start with the supply side: how many Turing machines are there? Every Turing machine is a finite object — a finite set of states, a finite tape alphabet, and a finite transition table, delta, spelling out delta(q, a) = (p, b, move) for each combination. Anything finite can be written down as a finite string of symbols. So each machine has a finite description, an encoding we usually write as the angle-bracketed string angle-bracket M angle-bracket. The machine IS, for counting purposes, just that finite string.
Now the key move. Fix any finite alphabet — say the symbols you use to write encodings. The set of ALL finite strings over a finite alphabet, the Sigma star you have known since the foundations rung, is countable. You can list every finite string by length: first all the length-0 strings (just epsilon), then all length-1 strings in alphabetical order, then all length-2 strings, and so on. Every finite string sits at a finite position in this list. Since each machine is one such finite string (and many strings are not even legal machine descriptions), the machines form a SUBSET of a countable set. A subset of a countable set is countable. So: there are only countably many Turing machines. You could, in principle, line up every machine that will ever exist as M_1, M_2, M_3, and not miss one.
There are uncountably many languages
Now the demand side: how many languages are there? Recall a language is just a set of strings — any subset of Sigma star. So the collection of all languages is the power set of Sigma star, the set of all its subsets. And here the sizes diverge. While Sigma star itself is countable, its power set is UNCOUNTABLE. There is no way to list all subsets of even a countably infinite set; the languages overflow any list you could write.
The proof is the same one Cantor used to show the real numbers are uncountable, repackaged for languages: diagonalization. Suppose, for contradiction, that you COULD list all languages as L_1, L_2, L_3, and so on. List the strings of Sigma star too, as s_1, s_2, s_3. Now build one rebellious language D, the diagonal language, by walking down the diagonal of the imagined grid and disagreeing with each listed language at one chosen string. The recipe: for each i, put the string s_i into D exactly when s_i is NOT in L_i. By construction D differs from L_1 on the string s_1, from L_2 on s_2, from L_i on s_i — it disagrees with the i-th language at the i-th string, for every i. So D cannot equal any L_i. Yet D is a perfectly good language. The list missed it. No list of languages can be complete, which is precisely what uncountable means.
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.
Counting forces undecidability
Put the two halves together and the conclusion is unavoidable. The languages are uncountable; the machines are countable. A countable supply cannot cover an uncountable demand — you cannot pair every member of an uncountable set with a distinct member of a countable set, the same way you cannot seat uncountably many guests on countably many chairs. So there MUST exist languages that no Turing machine recognizes at all. Since a decider is in particular a recognizer, those languages are certainly not decidable either. This is the theorem undecidable (in fact unrecognizable) languages exist, proved by a pure counting argument.
Sharpen it to feel how extreme it is. The languages with a recognizer form a countable subset of an uncountable whole. So if you imagine 'all languages' as a vast ocean, the recognizable ones are a countable scattering of droplets in it, and the decidable ones a still smaller scattering inside those. In the precise sense of these two infinities, ALMOST EVERY language is unrecognizable, and even more so undecidable. The machines we can build are the rare exception, not the rule. The familiar, well-behaved languages of this whole ladder live entirely in that thin recognizable sliver — which is exactly why they felt like the whole world until now.
What this opens up
So far the counting argument is silent about WHICH problems are the impossible ones. The shock of the rest of this rung is that the impossible problems are not exotic — they are questions you would love to answer about ordinary code. The flagship is the halting problem: given a machine and an input, will the machine eventually halt or loop forever? You will see that this single, eminently practical question is undecidable — not merely slow, not merely hard for big inputs, but impossible for ANY algorithm to answer in general, for every case, with a guaranteed halt. The proof reuses diagonalization, but now turned inward: a machine that asks about ITSELF and then deliberately does the opposite.
From the halting problem the impossibility spreads. A closely related language, the universal acceptance language A_TM — does machine M accept input w? — turns out to be recognizable but NOT decidable, and we will pin down a language that is not even recognizable at all (its complement). Then Rice's theorem generalizes the wreckage in one sweep: every non-trivial property of the LANGUAGE a machine recognizes is undecidable. Read that boundary carefully — it is about the language the program computes, not every syntactic property of the source text. Whether a program ever prints 'hello', whether two programs compute the same function, whether code matches its spec: all undecidable. The real-world toll is concrete: no general halt-checker, no perfect program-equivalence checker, no flawless bug-finder can exist. Counting told us the impossible was out there; the coming guides drag specific, useful problems into the light.