the undecidability of A_TM

Here is the keystone theorem: A_TM = { (M, w) : M accepts w } is undecidable. No Turing machine can always halt and tell you correctly whether a given machine accepts a given input. We already met the universal machine U, which recognizes A_TM by simulation; the new and deeper claim is that no machine can DECIDE it, that is, always finish with the right yes-or-no answer. The proof is the diagonal self-reference argument, applied directly to A_TM.

Assume, for contradiction, that some decider H always halts and correctly answers whether M accepts w. Build a machine D that takes a machine description M, runs H on (M, M), and then flips the result: if H says M accepts M, then D rejects (or loops), and if H says M does not accept M, then D accepts. Now run D on its own description. If D accepts D, then H must have said 'M does not accept M' with M = D, meaning D does not accept D — contradiction. If D does not accept D, then H must have said 'M accepts M', meaning D accepts D — contradiction. The assumed decider H cannot exist.

Why does this matter so much? A_TM is the seed from which nearly all later undecidability results grow, usually by reduction: to show some new problem B is undecidable, you show that a decider for B could be turned into a decider for A_TM, which we now know is impossible. The undecidability of A_TM (and the equivalent halting problem) is therefore the bedrock fact of computability — the first hard wall, against which every other impossibility theorem leans.