The Problem No Computer Will Ever Solve (Turing's Halting Problem)

Summer 1935, a meadow near Grantchester, outside Cambridge. A 22-year-old named Alan Turing is turning over a question the German mathematician David Hilbert had asked: is there a mechanical method that can settle any question written in the strict language of logic? A year later Turing proved the answer is no, and to do it he invented, on paper, the idea of a machine that follows any steps you give it. He described the limits of computers before anyone had built one. We go one level at a time: what a "computer" was in 1935 (a person doing sums by hand), the Turing machine (a paper tape, a head, a short list of rules, shown here really adding 1 to a binary number), why one machine can copy any other (the idea inside your phone), and the halting problem: why no program, the "Prophet", can always tell whether another program will finish or spin forever. The proof needs no math: build a "Rebel" that does the opposite of whatever the Prophet predicts, then feed the Rebel to itself. Then: why a faster computer doesn't help, how Alonzo Church reached the same answer another way, why your computer says "not responding" instead of "stuck forever", why no AI can fix this, and whether the same wall might apply to you. Sources Hodges, A., "Alan Turing: The Enigma" (Turing in the meadow at Grantchester, summer 1935), as described in the New York Review of Books, "Fall of a Genius" (1984) Turing, A. M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society (received 28 May 1936) MacTutor History of Mathematics, biography of Alan Turing (born 23 June 1912; the universal machine) "Turing's proof", Wikipedia (Hilbert's Entscheidungsproblem) On the later origin of the name "halting problem" (Martin Davis) and Turing's original form of the proof: arXiv 2407.00680 MacTutor History of Mathematics, biography of Alonzo Church (solved the Entscheidungsproblem in 1936 with the lambda calculus and published first) The Prophet, the Rebel, the human computer at her desk, the title page of the 1936 paper and the chat and code examples are our own drawings and made-up examples, not real documents or real chats. The tape machine on screen really runs: its three rules add 1 to a binary number (1011 becomes 1100). The speed chart shows a shape only, no real numbers. Painted scenes are illustrations; Alan Turing is shown only in real photographs. Photos (Wikimedia Commons) Alan Turing, 1936, Princeton University archives: public domain David Hilbert, 1907: public domain Human computers at NACA: NASA on The Commons, no known copyright restrictions ENIAC, Glen Beck and Betty Snyder at the Ballistic Research Laboratory: US Army, public domain Grantchester Meadows: Hugh Venables, CC BY-SA 2.0 Turing machine model by Mike Davey: photo by Rocky Acosta, CC BY 3.0 Icons: Material Design Icons (via Iconify). Chapters 0:00 Summer 1935: a meadow and a question 0:15 When computers were people 0:30 Hilbert's question 0:55 Turing's answer: no (1936) 1:26 Level 1: the machine 1:45 The Turing machine 2:23 It's inside your phone 2:36 Level 2: the spinning wheel 2:55 The Prophet 3:09 The halting problem 3:26 The Rebel 3:51 Feed the Rebel to itself 4:18 "This sentence is false" 4:31 Level 3: bigger, faster? 4:51 Alonzo Church hits the same wall 5:05 "Not responding" 5:18 Level 4: what about AI? 5:51 Turn it around: are you a Prophet? 6:06 The gym this week 6:20 Is your mind a Turing machine? 6:42 The line Turing drew 6:53 Wait, or close?