10
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Because the "seminal idea" was there. $\endgroup$
    – Mauro ALLEGRANZA
    Oct 17, 2015 at 9:29
  • 2
    $\begingroup$ As you said, it seems that the "first" discussion of the halting problem is included into the first textbook dedicated to Turing machine : Martin Davis, Computability and Unsolvability (1958), page 70. $\endgroup$
    – Mauro ALLEGRANZA
    Oct 17, 2015 at 9:44
  • 1
    $\begingroup$ See: en.wikipedia.org/wiki/Stigler%27s_law_of_eponymy So the gist is that it was done to honor Turing even though he didn't formalize the exact idea. $\endgroup$
    – MaxW
    Oct 22, 2015 at 6:48

1 Answer 1

Reset to default
3
$\begingroup$

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."

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.