Undecidability by Diagonalization

A decider for a language $L$ is a Turing machine that halts on every input and accepts exactly the strings in $L$, rejecting everything else. A language is decidable (recursive) if some decider exists for it, and undecidable if no such machine, however cleverly designed, can do the job. This is a statement about all possible algorithms, not about the limits of current technology — it is proven the way "no largest prime exists" is proven, by deriving a logical contradiction from the assumption that a solution exists. The central object of study is $A_{TM}$, the acceptance problem:

Here $\langle M, w \rangle$ denotes a fixed, computable encoding of the machine $M$ and string $w$ as a single string, so that $A_{TM}$ is itself a language over some alphabet. Because Turing machines can be encoded as strings, we can feed a machine's own description to another machine — including, crucially, to itself. This self-application is exactly what makes diagonalization possible, mirroring how Diagonalization and the Countability of Machines shows machines can be enumerated $M_1, M_2, M_3, \dots$ as strings, just like natural numbers. $A_{TM}$ is not hopeless: it is Turing-recognizable. The universal Turing machine $U$, on input $\langle M, w \rangle$, simply simulates $M$ running on $w$ step by step. If $M$ accepts, $U$ accepts; if $M$ rejects, $U$ rejects. The catch is that if $M$ runs forever on $w$, $U$ runs forever too — it never gets to announce "reject." A recognizer is allowed this asymmetry; a decider is not. The entire content of the undecidability proof is to show that this asymmetry cannot be repaired: no machine can be built that always halts and always gives the correct accept/reject verdict for every $\langle M, w\rangle$ pair.

The proof is a proof by contradiction built on self-reference, following the same skeleton as Cantor's diagonal argument, but applied to programs instead of infinite binary sequences.

Step 1 — Assume a decider exists. Suppose, for contradiction, that $A_{TM}$ is decidable. Then there is a Turing machine $H$ that halts on every input and satisfies:

Step 2 — Build a diagonalizing machine $D$. Using $H$ as a subroutine, construct a new machine $D$ that takes as input the description $\langle M \rangle$ of a single machine (not a pair), and does the following: feed $H$ the pair $\langle M, \langle M \rangle \rangle$ — that is, run $M$ on its own description. Then $D$ flips the answer: if $H$ says $M$ accepts $\langle M \rangle$, $D$ rejects; if $H$ says $M$ does not accept $\langle M \rangle$, $D$ accepts.

Step 3 — Run $D$ on itself. Since $D$ is itself a Turing machine, it has its own description $\langle D \rangle$, and nothing stops us from asking what $D(\langle D \rangle)$ does. Trace the definition:

This is a direct logical contradiction: $D$ accepts $\langle D \rangle$ if and only if $D$ does not accept $\langle D \rangle$. Since $H$ was assumed to be a total, always-correct decider, this contradiction is unavoidable once $D$ is run on its own description. The only resolution is that our initial assumption was false: no such $H$ exists, so $A_{TM}$ is undecidable. ``` // Assume, for contradiction, that H decides A_TM: // H(⟨M, w⟩) halts and outputs ACCEPT iff M accepts w. machine D(⟨M⟩): // input: description of a single TM M verdict := H(⟨M, ⟨M⟩⟩) // ask: does M accept its own description? if verdict == ACCEPT: return REJECT // flip the answer else: // verdict == REJECT return ACCEPT // flip the answer // Now run D on its own description: D(⟨D⟩): verdict := H(⟨D, ⟨D⟩⟩) // does D accept ⟨D⟩? if verdict == ACCEPT: return REJECT else: return ACCEPT // By definition of H: verdict == ACCEPT iff D accepts ⟨D⟩ // By definition of D: D accepts ⟨D⟩ iff verdict == REJECT // Combining: D accepts ⟨D⟩ iff D does not accept ⟨D⟩ — contradiction ``` The pseudocode is not a program you would ever "run" in practice — it is a proof device. Its only job is to expose that the hypothetical $H$, if it existed, could be forced into answering a question incorrectly about a machine built from itself. Every step uses only operations $H$ is assumed capable of (simulate $H$, branch on its output, halt) — no hidden assumption is smuggled in. The diagram below shows the logical dependency: $D$ is built using $H$, and then $D$'s own description is fed back into $D$, closing a loop that $H$ cannot consistently answer.

Deriving $HALT_{TM}$ undecidability by reduction. Define

Suppose, for contradiction, that a decider $R$ exists for $HALT_{TM}$. Build a decider $S$ for $A_{TM}$ as follows: ``` machine S(⟨M, w⟩): if R(⟨M, w⟩) == "does not halt": return REJECT // M loops forever, so it never accepts w else: simulate M on w to completion // safe: R guaranteed M halts on w if M accepted w: return ACCEPT else: return REJECT ``` $S$ always halts: the call to $R$ halts by assumption, and if $R$ reports "halts," the simulation of $M$ on $w$ is guaranteed to terminate, so the simulation step also halts. $S$ is correct: it accepts exactly when $M$ actually accepts $w$. So $S$ would decide $A_{TM}$ — but we already proved no decider for $A_{TM}$ exists. This contradiction shows $R$ cannot exist, so $HALT_{TM}$ is undecidable.

There is no "running time" to analyze here, because the theorem's content is that no algorithm exists at all, regardless of time or space budget — the complexity claim is not "slow," it is "impossible." This distinguishes undecidability from intractability (e.g., NP-hardness): an NP-hard problem has algorithms, just conjectured-slow ones, whereas $A_{TM}$ has none whatsoever, not even ones running in astronomical time or space.

Correctness of the $A_{TM}$ proof (why the contradiction is airtight): 1. $D$ is a well-defined Turing machine, assuming $H$ exists. $D$'s description is: "on input $\langle M \rangle$, construct the pair $\langle M, \langle M \rangle\rangle$, run $H$ on it, and output the opposite of $H$'s answer." Every step (string construction, running $H$, flipping output) is mechanical and always terminates, because $H$ is assumed to be a total decider. So $D$ itself is total: $D$ halts on every input. 2. $D$ has a description $\langle D \rangle$, and nothing prevents applying $D$ to it. This is the encoding argument from Diagonalization and the Countability of Machines: every Turing machine, including $D$, has a finite string encoding, and any machine — including $D$ — can be given any string, including its own encoding, as input. There is no type restriction in the model preventing self-application. 3. The contradiction is forced, not chosen. We do not get to decide what $D(\langle D\rangle)$ outputs; it is fully determined by $D$'s code and $H$'s (assumed) correct behavior. Tracing the definition mechanically yields "accepts iff it does not accept" — a proposition that is false under both truth values. In classical logic, a hypothesis that entails a contradiction must itself be false. The hypothesis was "$H$ exists and correctly decides $A_{TM}$"; therefore that hypothesis is false. 4. Why $A_{TM}$ is still recognizable. The contradiction relied on $H$ being total (always halting). The universal machine $U$ that simulates $M$ on $w$ is a valid recognizer precisely because it is allowed to loop forever instead of halting-and-rejecting; the proof's escape hatch is closed only for deciders, not recognizers. This is why $A_{TM}$ sits properly inside the Turing-recognizable languages without being decidable — it is the canonical witness that recognizable is strictly weaker than decidable.

Correctness of the reduction for $HALT_{TM}$: the argument follows the general schema of Mapping Reducibility: if $A_{TM} \le_m HALT_{TM}$ via a computable transformation using an assumed $HALT_{TM}$-decider $R$, then a decider for $HALT_{TM}$ would yield a decider for $A_{TM}$. Formally, $S$ built from $R$ is total (both its internal calls halt under the assumption) and correct (it accepts $\langle M,w\rangle$ exactly when $M$ genuinely accepts $w$), so $S$ decides $A_{TM}$ — contradicting the first theorem. This "reduce a known-undecidable problem to the new problem" pattern is the standard tool for proving new undecidability results without repeating a diagonalization from scratch each time.

Honest caveats. These proofs say nothing about specific, fixed programs — you absolutely can prove that particular programs halt (e.g., via loop invariants or termination measures). What is impossible is a single uniform algorithm that correctly answers the question for every machine-input pair, including deliberately adversarial or self-referential ones. Undecidability is a statement about the nonexistence of a universal method, not a claim that all instances are individually mysterious.

Since $D$ and $H$ are proof artifacts rather than runnable code (because $H$ cannot actually exist), a fully concrete numeric trace would be circular. Instead, we trace the logical computation precisely, using a toy stand-in to make the self-reference tangible, then verify the contradiction step by step. Suppose, purely hypothetically, that $H$ existed and that some machine $M_7$ has the property that $M_7$ accepts its own description $\langle M_7\rangle$. Trace what $D$ does on input $\langle M_7 \rangle$ versus on input $\langle D \rangle$:

Row 1 shows $D$ behaving perfectly sensibly on an ordinary input $M_7$ — no contradiction there, because $M_7 \ne D$. The contradiction appears only in rows 2–5, exactly when the input equals $D$'s own description. Both possible values of $H$'s answer (ACCEPT in row 2, REJECT in row 4) lead to $D$ doing the opposite of what was assumed. There is no third option in a decider's output space (deciders only output accept/reject and always halt), so every possible behavior of $H$ is refuted. This exhaustive case-split is what makes the contradiction unconditional rather than a fluke of one branch. A second, complementary trace shows the derived $HALT_{TM}$ result concretely using a genuinely simulatable machine. Let $M_{\text{loop}}$ be the machine "on any input, move the head right forever, never halting," and $w = \texttt{ab}$.

This table shows $S$ works flawlessly whenever $R$ works flawlessly — which is exactly the point: the reduction itself is a perfectly correct, terminating, honest algorithm. The impossibility lives entirely inside the assumption that $R$ exists, which the first (diagonalization) proof already ruled out.

Compilers and static analyzers routinely need to ask questions equivalent to "does this code path ever execute" or "does this loop terminate" — and the undecidability of $HALT_{TM}$ is the formal reason these tools must settle for sound-but-incomplete answers (they say "maybe" rather than a guaranteed yes/no). Antivirus and malware-detection systems face the same wall: a perfect, general "does this program ever perform a malicious action" detector cannot exist, which is why real detectors rely on heuristics, sandboxed execution with timeouts, and signature matching rather than a guaranteed decision procedure. Type checkers and verification tools (model checkers, SMT-based verifiers) are carefully designed to check decidable fragments or accept incompleteness, precisely to stay on the correct side of this boundary. In programming language design, the deliberate choice to make certain type systems Turing-complete (like C++ templates) versus deliberately weaker (like many dependently-typed proof assistants' termination checkers) is a direct engineering response to this theorem. Even IDE features like "will this recursive function definitely terminate" are, in full generality, asking an undecidable question, which is why linters flag suspicious patterns rather than proving termination outright.

Ask the tutor: How does Rice's Theorem generalize this diagonalization argument to show that every nontrivial semantic property of programs is undecidable?