From 'some language is undecidable' to a language you can name
The previous guide left you with a haunting but abstract fact: there are more languages than there are machines, so undecidable languages must exist. That was a counting argument — it tells you the missing answers are out there, like proving a haystack contains a needle without ever pointing at one. This guide does the pointing. We will exhibit a concrete, useful, perfectly natural question and prove it has no decider at all. Its name is the halting problem, and once you have met it, undecidability stops being a population statistic and becomes a thing you can hold.
First, a piece of machinery you already met on the Turing-machine rung but which now does heavy lifting: any Turing machine M can itself be written down as a finite string of symbols — its states, its transition table, all of it — exactly the way a program is just text in a file. We write that string as ⟨M⟩, the encoding of M. This is the quiet superpower of the whole subject: because a machine is just data, one machine can take ANOTHER machine's description as input and reason about it. A program can read a program. That single observation is what makes self-reference — and therefore the trap we are about to spring — possible.
Now state the question precisely, because the precision is where the difficulty hides. The halting problem asks: given the code of a machine M and an input w, will M eventually halt (stop) when run on w, or will it loop forever? As a language, we bundle the yes-instances into one set, written HALT = { ⟨M, w⟩ : machine M halts on input w }. Asking 'is the halting problem decidable?' is exactly asking 'is the language HALT decidable?' — is there one fixed machine that, fed any pair ⟨M, w⟩, always halts and correctly answers yes-it-halts or no-it-loops?
The universal machine: a machine that runs other machines
Before the bad news, some genuinely good news that we will need as a tool. There IS a single machine that can simulate any other machine. Feed it ⟨M, w⟩ and it faithfully mimics, step for step, what M would do on w — it is the universal Turing machine, the great-grandparent of every interpreter and CPU you have ever used. Your laptop is a universal machine: it does not have separate circuitry baked in for each app; it reads the app (the data ⟨M⟩) and runs it. That this is even possible — one fixed machine that becomes any machine you describe — is the deepest practical idea in all of computing.
The language this universal machine is built around has its own name: A_TM, the universal acceptance language, defined as A_TM = { ⟨M, w⟩ : machine M accepts input w }. Notice the difference from HALT: HALT asks whether M halts at all; A_TM asks the slightly different question of whether M halts and accepts. The two are close cousins, and proving one undecidable proves the other undecidable by a short reduction, which a later guide spells out. Here is the crucial half-truth: A_TM is recognizable. Just run the universal machine on ⟨M, w⟩; if M accepts w, your simulation will reach M's accept state and you say yes.
But — and this is the whole drama — recognizable is not decidable. If you simulate M on w and the simulation is still grinding after a billion steps, you are stuck in exactly the loop-or-not dilemma from the decidability rung: maybe M is about to accept, maybe it will reject in a moment, maybe it will run forever and you will wait forever with it. You cannot, in finite time, safely declare 'M does not accept w', because that would require knowing M loops, which is the very thing you have no way to detect. So A_TM is a recognizer's dream and a decider's nightmare. The next section proves the nightmare is unavoidable.
The trap: a machine that asks about itself and does the opposite
The proof that A_TM (and with it the halting problem) is undecidable is a diagonalization argument, the same self-referential weapon Cantor used to show the real numbers outnumber the whole numbers. The strategy is proof by contradiction: assume, just for the sake of argument, that a decider exists, then build a machine that drives that decider into a logical impossibility — a machine that, by construction, cannot consistently exist. The villain of the story is a tiny machine that asks a question about ITSELF and then deliberately does the contrary of whatever it is told. Let us walk it slowly.
- Assume the enemy exists. Suppose, for contradiction, that some decider H settles A_TM: given ⟨M, w⟩, H always halts and outputs ACCEPT if M accepts w, and REJECT if M does not (whether M rejects or loops). H never loops — that is the assumption we will blow up.
- Build a contrarian. Construct a new machine D that takes a single machine-description ⟨M⟩ as input. D internally calls H on the pair ⟨M, ⟨M⟩⟩ — that is, it asks H, 'does M accept its OWN description as input?' Then D does the opposite of H's answer: if H says M accepts, D rejects (or just loops); if H says M does not accept, D accepts and halts.
- Spring the trap: feed D its own description ⟨D⟩. Now ask the fatal question — what does D do on input ⟨D⟩? Inside, D consults H about whether D accepts ⟨D⟩, then does the opposite. So D accepts ⟨D⟩ exactly when H reports that D does NOT accept ⟨D⟩; and D fails to accept ⟨D⟩ exactly when H reports that it DOES.
- Read the contradiction. D accepts ⟨D⟩ if and only if D does NOT accept ⟨D⟩. That is a flat self-contradiction, like a barber who shaves exactly those who do not shave themselves. The only false step in the whole chain was the very first one — the assumption that H exists. Therefore no such H exists: A_TM is undecidable, and the halting problem with it.
Why is this called 'diagonalization'? Imagine an enormous table: one row per machine M, one column per input string, and in cell (M, w) you write whether M accepts w. The machine D is engineered to differ from EVERY machine M along the table's diagonal — at the cell where the row-machine is asked about its own description, D is built to disagree. A machine that disagrees with every row at the diagonal cannot be any row, yet D is a perfectly well-defined machine and so SHOULD be some row. The contradiction is that D both must and cannot appear in the list of all machines. The full table-and-diagonal picture is the heart of the next guide; here, hold on to the punchline: self-reference plus 'do the opposite' detonates any would-be universal halt-checker.
A language no machine can even recognize
The decidability rung gave you the slogan: decidable = recognizable AND co-recognizable. Run it backwards and it becomes a hammer. We just showed A_TM is recognizable (run the universal machine) but NOT decidable. By the theorem, A_TM therefore cannot ALSO be co-recognizable — if it were both, it would be decidable, which we have just refuted. So the COMPLEMENT of A_TM — the language of pairs ⟨M, w⟩ where M does NOT accept w — is a language that is not even recognizable. It is an unrecognizable language, and it is the first one most people ever meet by name.
Sit with how strange that is. For A_TM itself there is at least a machine that confirms the yes-answers — it just cannot confirm the no-answers. But for the complement of A_TM, there is NO machine that reliably confirms even the yes-answers (which here mean 'M does not accept w'). To confirm that M never accepts w, you would have to be sure M will not accept w on step number ten billion, or ten billion and one, or ever — and no finite amount of simulation can establish a forever. The honest takeaway: 'M loops on w' and 'M never accepts w' are statements with no positive witness you can finitely check. That is the qualitative leap from undecidable to unrecognizable, and it stacks the ladder of difficulty one rung higher than the halting problem itself.
Rice's theorem: it was never about halting in particular
You might hope the halting problem is a lone freak — one pathological question we can quarantine and otherwise carry on building tools. Rice's theorem crushes that hope with breathtaking generality. Stated carefully, it says: every NON-TRIVIAL property of the LANGUAGE a machine recognizes is undecidable. Unpack the two careful words. 'Property of the language' means a yes/no question that depends only on WHICH strings the machine accepts — its behaviour — not on how the code is written. 'Non-trivial' means at least one machine has the property and at least one does not (a property that holds for every machine, or for none, is trivially decidable — just always answer yes, or always no).
So questions like 'does this machine accept the empty string?', 'does it accept any string at all?', 'does its language contain a palindrome?', 'is its language regular?', 'does it accept exactly the even-length strings?' — every one of them is undecidable, because each is a non-trivial property of behaviour. The proof, which a later guide gives, is a reduction from the halting problem: a translator that turns any halting question into a question about whether some constructed machine has the property. Rice's theorem is why there is no general tool that decides, for arbitrary code, what the code MEANS.
What this costs real programmers
This is not an exhibit in a museum of mathematical curiosities; it is the bedrock under everyday software engineering. The halting problem says there is no general halt-checker — no tool that, given any program and input, always correctly tells you 'this will terminate' versus 'this will hang'. So your IDE's infinite-loop warning, however clever, must sometimes miss a real loop or cry wolf on code that is fine. Rice's theorem widens the damage: there is no perfect, fully-general bug-finder for any behavioural bug, no tool that decides for ALL programs whether two programs are equivalent, no decider for whether a function is ever called with a null argument across every possible run.
Read that ceiling correctly, though, because the practical lesson is hopeful, not defeatist. Undecidability forbids a single procedure that is CORRECT on EVERY input and ALWAYS halts. It does not forbid tools that are correct most of the time, or that are allowed to answer 'I don't know', or that work on a restricted, well-behaved sub-class of programs. Type checkers, linters, model checkers, termination provers, and the optimizing passes inside every compiler all live happily in this space: they sidestep Rice's theorem by being sound but incomplete (they never lie, but they sometimes shrug), or by analyzing only programs of a tamer shape. The theorem is a fence around the dream of a universal oracle, not around useful approximations.
One last guardrail, so you wield this correctly. Undecidability lives at the level of the all-powerful Turing machine, precisely BECAUSE it can do anything a real computer can. Drop down the Chomsky hierarchy and the walls fall away: for a finite automaton, emptiness, equivalence, and acceptance are all decidable, because a DFA is a finite, fully-mappable object with nowhere to hide an infinite loop. That is the same trade you have seen all the way up the ladder — power bought with unpredictability. The halting problem is the bill that comes due the moment your model becomes Turing-complete: as soon as your language can express arbitrary computation, it can express the contrarian machine D, and the wall snaps into place.