This will be a talk I shall give for the History and Philosophy of Science (HPS) Colloquium at the University of Notre Dame, 17 October 2025, 12:30-1:30 pm, 201 O’Shaughnessy Hall.
Did Turing ever halt?
Abstract. Alan Turing’s 1936 paper on computable numbers, perhaps one of the most impactful papers ever written, arguably spawned the fields of computability theory, complexity theory, and computer science, helping to usher in the computer age. He introduced Turing machines, provided the first universal computers, launched the investigation of the computable numbers, and proved the first instances of computable undecidability. Turing 1936 is widely credited, in nearly all the standard computability textbooks, for the undecidability of the halting problem, often viewed today as the seminal undecidability result, leading to all the others. The curious historical situation, however, is that there is no mention at all of the halting problem in Turing’s article and in fact Turing never considers the halting of his machines—he specifically designed them to run forever. In this talk (joint work with Theodor Nenu, Oxford), I shall discuss the curious history of the halting problem and the question of whether we rightly credit the undecidability result to Turing. I shall come eventually to a nuanced conclusion.
See the relevant paper:
Joel David Hamkins and Theodor Nenu, “Did Turing prove the undecidability of the halting problem?”, 18 pages, 2024, Mathematics arXiv:2407.00680.
Will this be available online for those who are not living in Europe?
Unfortunately, I don’t think it will be recorded. But you can find the paper at the link.