Why is the Halting problem attributed to Alan Turing?

Question

The halting problem is a very famous example from computability theory of a problem that is undecidable. It is often said that the proof of its undecidability was given by Alan Turing, indeed wikipedia repeatedly says so.

However, Turing's paper "On Computable Numbers, with an Application to the Entscheidungsproblem" does not deal with the halting problem at all. As Charles Petzold writes in "The Annotated Turing", page 234:

The halting problem has subsequently become closely identified with Turing Machines, but the concept is foreign to Turing's original paper.

The problems that Turing's paper does show are undecidable are the problem of deciding whether a Turing machine is circle-free (which is not the same as halting, since both circle-free and circular machines can keep printing forever), that of deciding whether a machine ever prints some specific symbol, and that of the Entscheidungsproblem. Of course, the problem of deciding whether a Turing machine is circle-free is very close to the halting problem, but it is nonetheless not the halting problem. I am aware that the term "halting problem" was coined by Martin Davis in 1958.

My question is, if Alan Turing never discussed the halting problem, why do so many sources attribute it to him?

Answer 1

In my opinion, it's because Turing's proof of the "circularity question" in On Computable Numbers, with an Application to the Entscheidungsproblem is close enough to the Halting Problem to warrant giving him credit. As you note, the phrasing is in terms of circle-free nonhalting machines rather than machines that "halt" but the idea is exactly the same. Rephrasing the problem in terms of halting rather than circularity (which Kleene and Davis, who like Turing were both students of Church, did as early as 1952) doesn't change the essence of the result.

Here is Turing's actual statement:

"The fallacy in this argument lies in the assumption that § is computable. It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps."