The Church-Turing Thesis lies at the junction between computer science, mathematics, physics and philosophy. The Thesis essentially states that everything computable in the “real world” is exactly what is computable within our accepted mathematical abstractions of computation, such as Turing machines. This is a strong statement, and, of course, if one had tried to say the same thing about natural laws and Newtonian physics, one would have a respectable thesis that turned out to be false. (There is even a theoretical research area, hypercomputation, that attempts to show how “super-Turing” computers could be built in real life by taking advantage on non-Newtonian physics.)

When I learned the Church-Turing Thesis in school, I was told that it was a thesis, not a theorem, precisely because it was not formally provable. The notion of “computable” was intuitive, not mathematically precise, so it was impossible to say whether a particular mathematical abstraction was the ULTIMATELY CORRECT one. Nevertheless, in 2008, two respected researchers — Nachum Dershowitz of Tel Aviv University, and Yuri Gurevich of Microsoft Research – did indeed publish a proof of the Church-Turing Thesis in the Bulletin of Symbolic Logic. How is this possible? They constructed an axiomatization of computation based on abstract state machines, a theoretical notion developed by Gurevich that Microsoft has used to perform practical software tests, and then proved that the Church-Turing Thesis held for that axiomatization of computation. In other words, they managed to formalize the notoriously unformalizable “computation in the real world.”

This impressed me quite a bit — so much so, that when a user named Avinash asked on the theoretical computer science question and answer site, “What would it mean to disprove Church-Turing Thesis?” I answered that the Thesis had been proved for all practical purposes. Not my finest hour, as we will see. Fortunately, Avinash, in a feat of crowdsourcing genius, accepted my answer as correct, in order to encourage discussion. Since then, some of the top theorists in the world have contributed their opinion of the Dershowitz/Gurevich paper, and their philosophy about the thesis overall. I will cover some of the main points in the rest of this blog entry. Continue reading →

### Like this:

Like Loading...