3 ms·
Turing didn't prove the halting problem was undecidable. The halting problem was defined after Turing's death by Martin Davis. Really? I did not include a refe
by lacker 5y ago
Turing didn't prove the halting problem was undecidable. The halting problem was defined after Turing's death by Martin Davis.
Really? I did not include a reference link here but I grabbed the dates from Wikipedia, which states:
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
Obviously Wikipedia is not the end-all be-all of mathematical sources, but I'd be curious to see a source that contradicts it here.
- chalst 5y agoThe Wikipedia article is sound and it also documents that Martin Davis came up with the term "halting problem" for a lecture he gave in 1952. He used Turing machines in his 1958 book. Turing machines are still a commonly used formalism in some areas of theoretical computer science.