Did Turing Prove the Halting Problem? His 1936 Proof vs. the Modern Proof

The familiar modern proof assumes a halting predictor, reverses its prediction, and feeds a program its own description. It is elegant—but not the argument Turing wrote. This animation reconstructs Turing’s actual route: Turing machines and descriptions, circular versus circle-free computation, the β and β′ diagonal arguments, the printing problem, and finally the Entscheidungsproblem. Turing did not formulate the modern halting problem or give its canonical proof, but he established its central machinery and proved closely related undecidability results. PAPERS Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem” https://www.cs.virginia.edu/~robins/T... Joel David Hamkins and Theodor Nenu, “Did Turing Prove the Undecidability of the Halting Problem?” https://doi.org/10.1093/logcom/exaf075 CHAPTERS 00:00 The question 02:11 The modern halting proof 03:57 What Turing did—and did not—write 04:20 How a Turing machine works 06:13 Circular and circle-free machines 08:42 Descriptions and computable sequences 11:03 The universal machine 11:30 Three diagonal arguments 17:08 Turing’s β′ construction 22:32 The self-blocking K-stage 26:25 Halting versus circle-freeness 29:35 The symbol-printing problem 34:37 The Entscheidungsproblem 41:06 Who proved the halting theorem? 43:05 Two proofs, two histories #AlanTuring #HaltingProblem #Computability