JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Counting the Uncountable: Diagonalization

Some infinities are bigger than others, and that single fact forces a stunning conclusion: there are more languages than there are machines, so some languages can never be recognized by any program. We build the diagonal argument from scratch and watch it crack the halting problem.

Two sizes of infinity

We end this rung with the most jaw-dropping idea in the whole toolkit, and it grows straight out of the simple notion of matching things up. Two collections are the 'same size' if you can pair their members one-to-one with nothing left over — a perfect bijection, like matching every left shoe to its right shoe. A set is countable if you can line all its members up in a single infinite list, item 1, item 2, item 3, and so on, so that everything appears somewhere. The counting numbers are countable by definition; less obviously, so are the integers, the fractions, and — crucially for us — the set of all finite strings, Sigma-star (written Σ*).

Why is Σ* countable even though it is infinite? Because you can list its strings in a sensible order: first by length, and within each length alphabetically. Over the alphabet {a, b} the list begins epsilon, a, b, aa, ab, ba, bb, aaa, and so on. Every finite string, no matter how long, appears at some finite position. This trick — list short ones first, never let length explode before you have covered everything below it — is the standard recipe for showing a set is countable.

Cantor's diagonal: a list that must be incomplete

Here is Cantor's argument, the engine of everything that follows. Suppose someone claims to have a complete numbered list of all infinite binary sequences (think infinite strings of 0s and 1s). We will manufacture a sequence that cannot be on their list, proving the claim was wrong — and since they were arbitrary, no such list can ever be complete. This is the diagonalization move, and it is a proof by contradiction wearing a very specific costume.

  1. Lay the alleged complete list in a grid: row n is the n-th sequence, column m is its m-th bit. So the table holds bit B(n, m) at row n, column m.
  2. Walk the main diagonal — the bits B(1,1), B(2,2), B(3,3), ... — picking up exactly one bit from each row, the one where the row number equals the column number.
  3. Build a new sequence D by flipping every diagonal bit: the m-th bit of D is the opposite of B(m, m). Where the diagonal says 0, D says 1, and vice versa.
  4. Now ask: can D be row n for any n? No — by construction D differs from row n at position n (we flipped exactly that bit). So D disagrees with every single row somewhere, and cannot be anywhere on the list.

The list was supposed to contain every infinite binary sequence, yet D is an infinite binary sequence that it misses. Contradiction. So no list can contain them all: the infinite binary sequences are uncountable — a strictly bigger infinity than the counting numbers. The genius is the diagonal: by disagreeing with row n at exactly position n, the new object is guaranteed to dodge the whole list at once, in a single sweep. Keep that picture; the next argument is the same picture with machines.

More languages than machines

Now we cash the idea in. A program — a Turing machine, that endless notebook you can read, erase, and rewrite — is itself just a finite description, a finite string of symbols. So the set of all programs can be listed: program 1, program 2, program 3, ..., exactly the way we listed Σ*. There are only countably many machines. That is a hard, honest limit on how many problems any machinery could ever solve, because each machine recognizes at most one language.

But how many languages are there? A language over Σ is just a subset of Σ* — a yes/no verdict on each of the countably many strings. Pin the strings down as string 1, string 2, string 3, ... and a language becomes an infinite sequence of bits: bit m is 1 if string m is in the language, 0 if not. That is precisely an infinite binary sequence — and we just proved those are uncountable. So there are uncountably many languages, but only countably many machines to recognize them. The counting argument then lands with full force.

Diagonalizing the halting problem

The counting argument tells us some uncomputable language is out there but stays maddeningly vague about which. To name a concrete villain, we run the diagonal trick again — this time the grid's rows are machines, the columns are inputs, and the entries are 'does it halt?'. This is the diagonalization of the halting problem, and it is famous for good reason: it shows the halting problem is undecidable, meaning no program can correctly predict, for every program-and-input pair, whether that run eventually halts or loops forever.

Suppose, for contradiction, a perfect halt-checker H exists. Feed H two things — a machine M and an input w — and it always halts and answers 'yes, M halts on w' or 'no, M loops on w'. We build a saboteur D that takes one input, a machine description M, and does the opposite of what M would do on its own description: D asks H whether M halts on input M; if H says 'halts', D deliberately loops forever; if H says 'loops', D promptly halts. D is the diagonal — it disagrees with each machine exactly on that machine's own self-description, the entry on the main diagonal.

Assume H(M, w) decides: "does machine M halt on input w?"

Build D, which takes one input -- a machine description M:

    D(M):
        if H(M, M) says "M halts on M":
            loop forever        <- do the OPPOSITE
        else (H says "M loops on M"):
            halt                <- do the OPPOSITE

Now run D on its OWN description:  what is  D(D) ?

    If D(D) halts   -> H(D, D) said "halts" -> D was built to loop. Contradiction.
    If D(D) loops   -> H(D, D) said "loops" -> D was built to halt. Contradiction.

Either way: impossible. So the assumed H cannot exist.
The self-referential diagonal: feeding D its own description forces a contradiction either way.

Now ask the diagonal question: what does D do when run on its own description, D(D)? If D(D) halts, then H must have said D halts on D, but D was built to loop in that case — contradiction. If D(D) loops, then H said D loops on D, but D was built to halt — contradiction. Every branch is impossible, so the only false assumption was H itself: no perfect halt-checker can exist. The same self-disagreement that broke Cantor's list breaks the dream of a universal halting oracle. This self-reference — a program reading its own description — is the engine, and it echoes the liar paradox, the sentence that says 'this sentence is false.'

What this really means (and what it does not)

Be precise about the conclusion, because it is easy to overstate or understate. The halting problem is undecidable: no single algorithm halts on every input and always gives the right halts-or-loops verdict. This is not 'we have not found a fast enough method yet,' and it is not 'the problem is merely very slow.' It is a permanent, mathematical impossibility — no future hardware, no cleverer code, and no quantum computer changes it, because the contradiction is logical, not a matter of speed.

Two honest caveats keep the result in its lane. First, undecidable does not mean 'unanswerable for any particular case' — you can often tell whether a specific program halts; what is impossible is one method that works for all of them. Second, undecidable is a different and stronger failure than merely being unrecognizable. The halting language is actually Turing-recognizable: a machine can confirm halting by just simulating and waiting, but if the input loops forever the simulation also loops forever and never reports 'no.' Recognizable but not decidable — a recognizer may run forever — is exactly the gap diagonalization opens, and you will explore it fully in the decidability rung.

Step back and admire the through-line of this whole rung. The pigeonhole principle proved that crowding forces a repeat; structural induction proved properties across infinitely many built-up objects; and diagonalization, the close cousin we promised at the end of the induction guide, proves that two infinities can fail to match, and uses a self-disagreeing diagonal to manufacture the one object that escapes any list. These four proof moves — induction, pigeonhole, the proof techniques from guide two's logic, and diagonalization — are the entire mathematical spine the rest of the ladder rests on. From here, every theorem about what machines can and cannot do is built from these bricks.