asks whether a general algorithm can decide in advance whether a program will ever finish or run forever, and it is almost always credited to Turing’s 1936 paper. A piece of logical and historical work went back to the paper itself. What is actually in it?
Everything except that statement. Turing built the whole foundation there, and the idea of the universal machine, and proved several similar problems undecidable. The specific formulation taught today never appears in the paper explicitly. It is , and the point is and not the contribution.
The 1936 paper is the foundation stone of computer science, and that is not in doubt. It defines the Turing machine, presents the idea of a universal machine that runs a description of another machine, and proves several problems undecidable.
What the 2024 work checks is narrow and specific: whether the familiar formulation of the halting problem, as it appears in every textbook, is in there. The check was an orderly comparison between what Turing stated and proved and what is quoted in his name.
The conclusion is that the formulation is not in the paper. The problems Turing proved are very close and stated differently, the whole foundation is there, and the exact formulation settled later, as the field entered textbooks and needed a clean presentation.
It matters not to turn this into something it is not. There is no claim that Turing failed to contribute or that somebody else proved it, only a precision about attribution. And the lesson is more general: even an attribution that sounds obvious is worth checking against the source, because a story retold tends to straighten and shorten.
wat. The exact formulation of the halting problem taught in every computer science course is not in Turing’s paper.
wat wat
It is a reminder that even a basic, familiar attribution is worth checking against the original, instead of relying on the way it has been retold over and over.
How do we know?
The work carefully compares what Turing stated and proved in the original paper against the modern formulation credited to him in textbooks, and points out the gap between the two.
What is still unknown
The work does not claim Turing failed to contribute to the foundations of the problem, only that the exact formulation credited to him is not in the paper itself.
Learn something?
Where to next
Why is there always one point in the coffee that did not move?proof
How many colors does it take to color any map?proof
Can every true statement in mathematics be proved?logic