Turing Oversold?

He first says that Church was Turing's advisor without citing that Church became Turing's advisor only after both of them independently solved the Entscheidungsproblem.

Also, it is only after Turing became aware of Church's solution that he wrote an appendix to his work where he cited Church and showed that both solutions were equivalent. And even through the solutions were equivalent, the techniques employed were very different. Church even stated that Turing machines were more intuitive and praised Turing's work.

About Turing citing Gödel, the problems they solved were related but not the same. To put it informally, Gödel showed that in every useful axiomatic system, there would theorems that could neither be proved true or false. To do this, he codified math and derived such theorem. On the other hand, Turing showed that there was no general way of deciding if a theorem was true, false on unprovable. To do this, Turing defined a model of computation that we now call Turing machines.

Both Turing and Church defined the first two (and equivalent) models of computation. After this, many new models emerged and none of them were shown to be more powerful (in relation to what it computes) than Turing machines or Lambda Calculus. That is why we now believe in what we call the Church-Turing thesis: Everything that is computable is computable by a Turing machine.

I see many people in the comments praising the article because of the number of citations. This is not a good metric to judge one's work. I do not have the time to make a reference to everything that I said above, but if one is curious they can find all of them in Charles Petzold's book The Annotated Turing. If one is interest in this topic, I also recommend the Stanford Encyclopedia of Philosophy and the book Gödel's Proof.

About the rant the article makes about over attributing a person contributions, I can only say that this is a problem that has no solutions. One example I like to give is Wiles' proof of Fermat's Last Theorem. We say that Wiles proved Fermat's Last Theorem, which is true, but we may also say that Wiles "only" did the last step in proving Fermat's Last Theorem, before him many other people tried, advanced and contributed to our understanding of the problem so Wiles could finally prove it. For me personally, I know that every advance in science is made in the shoulder of giants and do not bother with attribution, since this is a topic we could discuss all day without going anywhere. About the particular example of Turing, I am Computer Scientist working with Theory of Computation and Computational Complexity who is familiar with the history and pioneer work done by Turing and do not believe he is oversold, not in the academic community nor in popular culture.

Among so much that’s just plain wrong, I really dislike the insidious idea that Turing’s horrible punishment at the hands of the state was wrong because he was a unique genius and war hero. No, it was wrong because he was a human being and being gay should not be a crime!

That line of thought makes it harder to argue that no, Turing may have been a genius but wasn’t unique, he was just a significant player in a rich field. That doesn’t make him any less interesting.

https://en.wikipedia.org/wiki/Von_Neumann_architecture

von Neumann simply described the work of Eckert and Mauchly on the ENIAC in a written report. And his name was on the report which made people think that he came up with the idea, which was false. It also resulted in a patent dispute -- it's interesting to imagine what would have happened if the concept had been patented. The book goes into detail on this.

The wikipedia article also talks about Turing machines as a precedent that store data and code in the same place. But ironically I'd say that probably gives him too much credit! I think a large share should go to the people who designed a working machine, because it's easy to say come up with the idea of an airplane; much harder to make it work :) And to me it seems unlikely that the Turing Machine, which was an idea created to prove mathematical facts, was a major inspiration for the design of the ENIAC.

Finally, even though the author of this web page has his own credit dispute, I appreciate this elaboration on the credit assigned to Turing.

If there was no narrative, no idols, no celebrities, would people be less motivated to do science? Why do we need to lie to ourselves so?

> If you're already deeply interested in computer science, of course the detailed narrative recognizing dozens of brilliant early computer scientists is richer. Of course!

Personally I'm mostly uninterested in who did what, but maybe that's just me. It seems obvious to me that nearly every scientific discovery could have been done equally well by millions of people, it's just a matter of who had the resources to be educated, who decided to research the problem, who managed to snipe the answer first, and who had the right connections to get it acknowledged. They're still great achievements, for sure, but they're not the markers of exceptional genius we want to think they are, not for Turing or Einstein, but not for anyone at all, really.

Goedel apparently believed that it was impossible to explicitly enumerate all the partial computable functions over the integers, until Turing proved him wrong. He reasoned as follows:

- You can't enumerate the total functions because Cantor's diagonal argument is constructive. Given a claimed enumeration of N^N, you can perform Cantor's diagonal construction to produce a computable element of N^N not in the enumeration. So N^N is computably uncountable.

- Classical set theory says that a superset of an uncountable set is also uncountable.

The problem is that while a superset of an uncountable set is uncountable, a superset of a computably uncountable set may instead be computably countable. The partial functions over the integers show that this is indeed the case.

Cantor's construction is blocked because a partial function can output a degenerate value called non-termination. A computable function must map the non-termination value to itself. Since it isn't mapped to something different, Cantor's construction can't produce something outside an enumeration.