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

The Diagonalization Proof

Guide 1 counted that undecidable languages must exist; guide 2 named the most famous one. Now we build the actual machine that breaks every would-be halt-checker — a program handed its own description that is rigged to do the opposite of whatever the checker predicts — and follow the same contradiction outward to a language no Turing machine can even recognize, and on to Rice's theorem.

Where we are, and the one trick we are about to reuse

The first guide of this rung did the head-count: there are uncountably many languages but only countably many Turing machines, so most languages have no machine at all — undecidable, even unrecognizable, languages MUST exist. That was an existence proof: it told you the monsters are out there without showing you one. The second guide pointed at a specific, useful monster — the halting problem: given a program and an input, will it halt or loop forever? This guide does the thing the counting argument could not: it takes one concrete language and proves, by explicit construction, that no decider for it can exist.

The single trick that does all the work is diagonalization, and you have already met it. Back in the math rung, Cantor used the diagonal argument to show the real numbers are uncountable: list any supposed enumeration of reals, then build a new real that differs from the first listed number in its first digit, from the second in its second digit, and so on down the diagonal — the result cannot be anywhere in the list, contradiction. We are about to run that exact maneuver, but the 'list' is a table of machines versus inputs, and the 'flip a digit' step becomes 'do the opposite of what the machine does'. Same skeleton, computational flesh.

The table, and the diagonal that has no home

Here is the central fact we lean on: a program is just text, and text is just a string, so a Turing machine M can be written down as a finite string, written encoded as `<M>`. That means we can feed a machine's own description to a machine as input — a machine can read about a machine. Now imagine an enormous table. Down the left edge, list every Turing machine M1, M2, M3, ... (countably many, so they fit in a list). Across the top, list every input string — and since machine descriptions are themselves strings, use the descriptions `<M1>, <M2>, <M3>, ...` as the column labels. In the cell at row Mi and column `<Mj>`, write whether machine Mi accepts the string `<Mj>`: A for accept, anything-else (reject or loop) for not-accept.

             <M1>   <M2>   <M3>   <M4>  ...
        M1 [  A  ]   .      A      .
        M2    A   [  .  ]   .      A
        M3    .      A   [  A  ]   A
        M4    A      A      .   [  .  ]
        ...

   Read the boxed DIAGONAL: M1 on <M1>=A, M2 on <M2>=., M3 on <M3>=A, M4 on <M4>=.

   Now build D so it does the OPPOSITE down the diagonal:
        D on <M1> -> not A  (M1 said A)
        D on <M2> -> A      (M2 said .)
        D on <M3> -> not A  (M3 said A)
        D on <M4> -> A      (M4 said .)

   D's behaviour on <Mi> differs from Mi's at every i, so D is NO ROW in the table.
   But every machine is a row. So D cannot be a machine.  Contradiction.
The acceptance table. The diagonal asks each machine about its own description; the new machine D is engineered to disagree with the diagonal cell by cell, so it cannot equal any machine in the list.

Stare at the diagonal — the cells where machine Mi meets its own description `<Mi>`. Now define a new machine D whose behaviour is, by design, the flip of that diagonal: D on input `<Mi>` accepts exactly when Mi does NOT accept `<Mi>`, and does not accept exactly when Mi does. Then D disagrees with M1 in column 1, with M2 in column 2, with M3 in column 3 — with EVERY machine somewhere. So D's row of behaviour matches no row in the table. But the table was supposed to list every machine. The only escape is that D is not on the list at all — D cannot be a Turing machine. Whatever ability we secretly assumed in order to build D is therefore impossible. The next section pins down exactly what that forbidden ability is.

The machine that asks about itself, then does the opposite

Let us make D concrete and see what it needs. The famous target is the universal acceptance language, written A_TM (the 'TM' is for Turing machine): A_TM = { `<M,w>` : M is a Turing machine and M accepts the string w }. A machine that recognizes A_TM is just a universal Turing machine — feed it a program and an input, and it simulates the program on the input, accepting if the program accepts. Universal machines clearly exist; that is what an interpreter is. The hard question is whether A_TM is DECIDABLE — whether some machine H can always HALT and correctly say yes-or-no for every `<M,w>`, including saying a clean 'no' when M would have looped on w. Assume, for contradiction, that such a decider H exists.

Using H as a subroutine, build a small, perfectly legal machine D that takes a single machine description `<M>` as input. D runs H to ask the self-referential question 'does M accept its own description `<M>`?' Then D does the OPPOSITE of H's answer: if H says M accepts `<M>`, then D rejects (halts, does not accept); if H says M does not accept `<M>`, then D accepts. Because H always halts (that was the whole assumption), D always halts too — D is a genuine, well-defined machine. So far nothing is paradoxical. The trap springs only when we run D on one very particular input.

  1. Feed D its OWN description: run D on the input `<D>`. By D's definition, D first asks H: 'does D accept `<D>`?' This is the self-reference move — the machine pointing the question back at itself.
  2. Case 1 — suppose H answers 'yes, D accepts `<D>`.' Then by D's wiring, D does the opposite and REJECTS `<D>`. So D does not accept `<D>`. But that contradicts H's 'yes'. Impossible.
  3. Case 2 — suppose H answers 'no, D does not accept `<D>`.' Then by D's wiring, D does the opposite and ACCEPTS `<D>`. So D does accept `<D>`. But that contradicts H's 'no'. Also impossible.
  4. Both of H's only two possible answers lead to a flat contradiction. The one thing we assumed into existence — the always-halting decider H — is the culprit. Therefore H cannot exist: A_TM is undecidable.

Following the contradiction outward: a language no machine can even recognize

A_TM is undecidable, but notice it is still RECOGNIZABLE: the universal machine recognizes it (simulate M on w; accept if it accepts; and if M loops on w, the simulation loops too — which is allowed for a recognizer). So A_TM lives in the gap from the previous guides: recognizable but not decidable. The natural next question is whether anything sits even further out — a language that no Turing machine can recognize at all, where you cannot even reliably get a 'yes'. The answer is yes, and we already have the tool to find one: the complement of A_TM.

Recall the clean three-ring picture from the decidability rung: a language is decidable EXACTLY when it is both recognizable and co-recognizable — that is, when both it and its complement are recognizable. Run that backwards. We just proved A_TM is recognizable but NOT decidable. If its complement the complement of A_TM were also recognizable, then A_TM would be both recognizable and co-recognizable, hence decidable — but it is not decidable. Contradiction. So the complement of A_TM cannot be recognizable: it is a genuinely unrecognizable language. This is the monster the counting argument promised but could not hand you: here it is, named and pinned down.

Rice's theorem: the contradiction generalizes to almost everything

A_TM is one undecidable question, but it feels like a single odd case. The shock of Rice's theorem is that it is not odd at all — undecidability is the rule, not the exception. Stated carefully: every NON-TRIVIAL property of the LANGUAGE a Turing machine recognizes is undecidable. Unpack the two careful words. A property is of the LANGUAGE (the set of strings the machine accepts), not of the machine's source text — questions like 'does this machine recognize the empty language?', 'does it recognize a regular language?', 'does it ever accept the string hello?'. And NON-TRIVIAL means the property holds for some recognizable languages but not all — it genuinely splits the machines into a yes-pile and a no-pile.

Why is the LANGUAGE-versus-CODE distinction doing so much work? Because many things you can check easily are properties of the code, not the language, and Rice does not touch them. 'Does this program have more than 100 lines?', 'does the source contain the word print?', 'does it have exactly 7 states?' — all decidable, because you just read the text. Those are not properties of the language the machine recognizes; two machines with wildly different source can recognize the very same language. Rice speaks only about the language, the behaviour, the WHAT-it-accepts — and any non-trivial fact about that is undecidable. The semantic questions are the hopeless ones; the syntactic ones can be fine.

And why must the property be non-trivial? The two TRIVIAL properties are the escape hatches that ARE decidable. 'Is the recognized language one that is recognizable?' is true of every machine — a decider can just always say yes, no work needed. 'Is the recognized language one that is NOT recognizable?' is false of every machine — always say no. Those two say nothing about the input, so they are trivially decidable. The instant a property actually distinguishes one recognizable language from another, Rice's theorem slams the door: deciding it would, by a reduction back to A_TM, let you decide the halting problem, which we just proved is impossible. The mechanism is the same diagonalized self-reference, wrapped in a reduction — the engine you will turn into a general weapon in the next guide.