Diagonalization and the Countability of Machines

A language over an alphabet $\Sigma$ is any subset $L \subseteq \Sigma^*$, where $\Sigma^*$ is the set of all finite strings over $\Sigma$. A Turing machine $M$ recognizes a language $L(M)$ consisting of exactly the strings on which $M$ halts and accepts. Since every Turing machine has a finite, fully written-out description (its states, transition function, alphabet), we can encode each machine as a single finite string $\langle M \rangle$ over a fixed alphabet — this is precisely the encoding scheme that makes the Universal Turing Machine possible, since a universal machine must be able to read $\langle M \rangle$ as ordinary input. Because every Turing machine has such a finite string description, and the set of all finite strings over any finite alphabet is countable, the collection of all Turing machines is countable. We can list them $M_1, M_2, M_3, \dots$ by, for instance, sorting all strings by length and then lexicographically, and discarding any string that fails to parse as a syntactically valid machine description. The set of languages is a different animal entirely. A language over $\{0,1\}$ can be identified with an infinite binary sequence — one bit per string in $\Sigma^*$, indicating membership — and Cantor's theorem shows the set of infinite binary sequences (equivalently, the power set of any countably infinite set) is uncountable. This is not "much bigger" in a vague sense; it is a strictly larger infinite cardinality, meaning no function from $\mathbb{N}$ to the set of languages can ever be surjective, no matter how ingenious. The crux of this article's payoff is a cardinality mismatch: countably many machines cannot cover uncountably many languages, because a countable set can be enumerated by $\mathbb{N}$ while an uncountable one provably cannot. Since each machine recognizes exactly one language, the map from machines to languages can hit only countably many targets — leaving uncountably many languages with no recognizing machine at all. This is the article's central theorem, and diagonalization is the engine that proves both halves of the mismatch.

The proof has three independent moving parts, each worth isolating before combining them.

Part 1 — Turing machines are countable. Fix a finite encoding alphabet, say $\{0,1\}$. Every Turing machine's formal description (its state set, tape alphabet, transition table, start/accept/reject states) can be written as a finite binary string $\langle M \rangle$, using a standard scheme (e.g., states as blocks of $0$s, transitions separated by $1$s). Enumerate all finite binary strings in "shortlex" order (by length, then lexicographically): $\epsilon, 0, 1, 00, 01, 10, 11, 000, \dots$. This produces a surjection from $\mathbb{N}$ onto all binary strings; filtering out strings that are not syntactically valid machine encodings still leaves a countable (possibly finite-per-length, infinite overall) enumeration $M_1, M_2, M_3, \dots$ of every Turing machine, each appearing exactly once.

Part 2 — Languages over $\Sigma^*$ are uncountable. Fix any countable enumeration attempt of languages, $L_1, L_2, L_3, \dots$, where $\Sigma^* = \{s_1, s_2, s_3, \dots\}$ is itself enumerated (this is possible since $\Sigma^*$ is countable). Build the diagonal language $D$ by flipping membership along the diagonal of the membership table:

Then $D$ differs from every $L_i$ in the list at the string $s_i$ (either $s_i \in D$ but $s_i \notin L_i$, or vice versa), so $D \neq L_i$ for every $i$. Since the list was an arbitrary attempted enumeration, no enumeration of all languages can exist — the set of languages is uncountable.

Part 3 — Combine. Every Turing machine $M_i$ recognizes some language $L(M_i)$ (possibly the empty language, if $M_i$ never accepts). This gives a countable list $L(M_1), L(M_2), L(M_3), \dots$ — potentially with repeats, but certainly at most countable. Apply the diagonal construction from Part 2 to this specific list. The resulting diagonal language $D$ differs from every $L(M_i)$, hence $D$ is recognized by no Turing machine whatsoever. $D$ is Turing-unrecognizable. ``` // Enumerate all Turing machines as finite binary strings. function ENUMERATE_MACHINES(): i := 0 for each binary string s in shortlex order: // ε, 0, 1, 00, 01, ... if s is a syntactically valid TM encoding: i := i + 1 M[i] := decode(s) // M[1], M[2], ... lists every TM return M // countably infinite list, no TM omitted // Enumerate all strings over Σ (needed to index the diagonal). function ENUMERATE_STRINGS(Σ): return all strings over Σ in shortlex order // s[1], s[2], s[3], ... // Build the diagonal language against an arbitrary countable list of languages. function DIAGONALIZE(L): // L[1], L[2], ... a countable list of languages S := ENUMERATE_STRINGS(Σ) D := {} for i := 1, 2, 3, ...: if S[i] not in L[i]: D := D ∪ { S[i] } // else: S[i] is left out of D return D // D ≠ L[i] for every i, by construction at S[i] // Main theorem: a language no machine recognizes exists. function EXISTS_UNRECOGNIZABLE_LANGUAGE(): M := ENUMERATE_MACHINES() L := [ L(M[i]) for i := 1, 2, 3, ... ] // L[i] = language recognized by machine M[i] D := DIAGONALIZE(L) // D differs from L(M[i]) for every i ⇒ no machine recognizes D return D ``` The key invariant maintained at every loop iteration of `DIAGONALIZE` is: after processing index $i$, $D$ and $L[i]$ disagree on membership of $S[i]$. This single-string disagreement, repeated across all $i$, is enough to guarantee $D \ne L[i]$ for every $i$ in the list — no matter how the list was generated, or how large it is (as long as it is countable).

This is a mathematical existence proof, not an algorithm meant to run efficiently, so "complexity" here concerns the logical structure and cost of the construction rather than runtime — though it is worth noting the diagonal language is not even effectively constructible in general, only definable.

Countability of Turing machines — correctness. Every valid encoding $\langle M \rangle$ is a finite string over a finite encoding alphabet. Shortlex order enumerates all finite strings in a well-defined sequence with each string at a finite, computable index, giving a bijection $\mathbb{N} \to \{\text{finite strings}\}$. Restricting to the subset of strings that parse as valid machine descriptions yields an injection from a subset of $\mathbb{N}$, which composed with the enumeration is still a surjection onto all Turing machines from $\mathbb{N}$ — hence countable. This uses only the finiteness of each individual machine description; no bound on how many machines exist is needed, since $\mathbb{N}$ itself is infinite.

Uncountability of languages — correctness. This is Cantor's theorem specialized to $\Sigma^*$. Suppose, for contradiction, some enumeration $L_1, L_2, \dots$ did list every language over $\Sigma$. Construct $D$ as above. By construction, for every index $i$: $s_i \in D \iff s_i \notin L_i$. This means $D$ and $L_i$ disagree specifically on the string $s_i$, so $D \neq L_i$ as sets. Since this holds for every $i$, $D$ is not equal to any language in the supposed complete list — contradicting the assumption that the list was exhaustive. This is a genuine proof by contradiction: the diagonal set is built precisely to defeat whatever enumeration is handed to it, which is the entire trick.

Why cardinality forces the conclusion. A set $A$ is countable if there is a surjection $\mathbb{N} \to A$. If $|A| \le |\mathbb{N}|$ (countable) and $|B| > |\mathbb{N}|$ (uncountable), no surjection $A \to B$ can exist — an injection from an uncountable set into a countable one is impossible, since composing it with the countable set's enumeration would enumerate the uncountable set. Here $A$ = Turing machines (countable), $B$ = all languages (uncountable), and the natural map $M \mapsto L(M)$ is a function $A \to B$. Since $|A| < |B|$, this function's image is a proper subset of $B$: the map cannot be surjective. Every language outside the image is unrecognizable by any Turing machine.

Honest caveats. This argument proves unrecognizable languages exist but does not exhibit a natural, meaningful one — the diagonal language $D$ depends on the arbitrary enumeration order chosen for both machines and strings, and is not itself a "naturally occurring" decision problem anyone would ask about. This is precisely why the field develops a second, sharper technique: rather than diagonalizing against an abstract enumeration, one diagonalizes against machines using their own encoded input — this is exactly the move that proves $A_{TM}$, the specific and meaningful language of "does machine $M$ accept input $w$," is undecidable, foreshadowing the Halting Problem as the natural, applications-relevant descendant of this counting argument.

Concreteness helps make the counting argument feel inevitable rather than a sleight of hand. Suppose (purely for illustration — real machine encodings are longer) that we have a toy enumeration of just four machines over $\Sigma = \{0,1\}$, and $\Sigma^*$ enumerated as $s_1 = \epsilon, s_2 = 0, s_3 = 1, s_4 = 00, \dots$

Reading the bolded diagonal gives the sequence Yes, No, Yes, No. The diagonal language $D$ is defined to flip each of these:

Now check $D$ against each machine's language directly:

• $D$ vs. $L(M_1)$: $L_1$ contains $s_1=\epsilon$, but $D$ does not contain $s_1$. They disagree ⇒ $D \ne L(M_1)$.
• $D$ vs. $L(M_2)$: $L_2$ does not contain $s_2=0$, but $D$ does contain $s_2$. They disagree ⇒ $D \ne L(M_2)$.
• $D$ vs. $L(M_3)$: $L_3$ contains $s_3=1$, but $D$ does not. They disagree ⇒ $D \ne L(M_3)$.
• $D$ vs. $L(M_4)$: $L_4$ does not contain $s_4=00$, but $D$ does. They disagree ⇒ $D \ne L(M_4)$.

In this toy four-machine world, $D$ is guaranteed different from all four listed languages — regardless of what the other, unshown entries of each row look like, because a single point of disagreement per row is all that set-equality requires to fail. Scaling this table to the full countably infinite enumeration of all Turing machines is exactly the proof: $D$ disagrees with $L(M_i)$ at $s_i$ for every $i \in \mathbb{N}$, so $D$ equals none of them, so $D$ is recognized by no Turing machine at all.

The diagonal method predates computability theory entirely, born out of pure set theory, and was only later imported into logic and computation as a general-purpose "impossibility engine."

The cardinality gap between machines and languages is not a curiosity confined to blackboards — it is the reason computer scientists accept, as a matter of course, that some well-posed problems have no algorithm at all, regardless of hardware, time budget, or cleverness. This shapes how real systems are designed: compiler writers and static-analysis tool builders know in advance that fully general "does this program have property X" checkers cannot exist for undecidable properties (a consequence sharpened by Rice's theorem, itself a diagonalization descendant), so they deliberately build conservative approximations instead of chasing an impossible perfect answer. The same reasoning underlies why formal verification tools, type checkers, and virus scanners all accept incompleteness by design — they are engineered to say "unknown" or "possibly" rather than promise a definitive yes/no on every input, because a definitive general procedure is provably out of reach. Programming language theorists cite this gap to justify restricting language expressiveness (e.g., total functional languages, decidable type systems) specifically to stay inside the "recognizable" or "decidable" side of the boundary this article draws. Historically, this argument is the direct scaffold beneath the Halting Problem: rather than diagonalizing over an abstract enumeration of languages, Turing diagonalizes machines against themselves, using self-application (feeding a machine's own encoding as its input) to derive a concrete contradiction. That sharper, self-referential version of diagonalization is the technique explored under Undecidability by Diagonalization, and it is what ultimately yields a specific, meaningful undecidable problem — $A_{TM}$ — rather than merely an abstract existence proof.

Ask the tutor: How does self-referential diagonalization (a machine analyzing its own encoding) sharpen this abstract existence proof into the concrete undecidability of the Halting Problem?