The Dershowitz/Falkovich proof of the Extended Church-Turing Thesis

In a previous post, I considered a proof of the Church-Turing Thesis that Dershowitz and Gurevich published in the Bulletin of Symbolic Logic in 2008.  It is safe to say that the proof is controversial — not because it is technically inaccurate, but because it relies on an axiomatization of computation that excludes randomness, parallelism and quantum computing.  (For more discussion of that paper, please see the previous blog entry, or the question about disproving the Church-Turing Thesis on CSTheory.)  Nevertheless, one of the authors, Dershowitz, and his PhD student Falkovich, have just published a proof of an even more controversial statement, the Extended Church-Turing Thesis.  It is this new proof which I will now discuss.

The Extended Church-Turing Thesis is the statement that every physically realizable computational device can be simulated efficiently by Turing machines.  (By contrast, the “mere” Church-Turing Thesis says that Turing machines can simulate any computational device, but perhaps at the cost of an exponential blowup in time and/or space.)  Unlike the Church-Turing Thesis, which computer science convential wisdom appears to think is true, many CS people believe the Extended Church-Turing Thesis to be false, because quantum computers are expected to be strictly stronger than classical computers.  (The most famous example of this difference in strength is a quantum algorithm that can factor large integers in polynomial time, due to Peter Shor.  Most CS people believe that classical computers cannot factor integers in polynomial time, and many cryptography programs depend on this infeasibility.)  Dershowitz and Falkovich sidestep this issue by attempting to axiomatize only “classical” algorithms — no quantum, no randomization, no massive parallelism.  They define an algorithm’s implementation, a program, an efficient program, and then prove that any efficient program (in their general axiomatic sense) can be simulated in linear time by a Random Access Machine (RAM).  Since a RAM can be simulated efficiently by a Turing machine, the Extended Church-Turing Thesis follows as a consequence.

First technical post now up on CSTheory Community Blog

The first technical post is now up on the CSTheory Community Blog.  It is Quantum Query Complexity, by Artem Kaznatcheev.  Artem is currently working on a followup post on the “negative adversary method,” a fairly recent proof technique in quantum computing, which we will post there soon.

I hope you enjoy the new blog!  I think this is a great first post.  Thanks very much, Artem.  And, everyone else, if you would like to participate, either on a one-time basis, or regularly, please add your name to the blog contributor signup sheet, or email me or Joe Fitzsimons directly.  Thank you.

The SZR model of the zombie apocalypse

You’ve watched all the movies.  You’ve read all the books.  You’ve even practiced tactial skirmishes with lifesize zombie targets.  But now, all of a sudden, you are thinking, “I didn’t know there would be math!”

Actually, if you’re a regular reader of this blog, I imagine you are thinking, “I didn’t know there would be zombies.”  For those who want a math-free overview of Munz et al.‘s “When Zombies Attack: Mathematical Modelling of an Outbreak of Zombie Infection,” please see this piece by Wired.  For the rest of you, I promise Greek letters and differential equations after the jump.

Acknowledgement: I would like to thank blame this post on Dave Clarke, who brought the Munz et al. paper to my attention in an answer he gave to a question I asked about the computational theory of simulation of diseases.

New blog: Theoretical Computer Science

Quantum computing expert Joe Fitzsimons and I have just agreed to be co-editors of the brand-new blog Theoretical Computer Science, the community blog of the TCS question and answer site cstheory.stackexchange.com.  The first post of the new blog is here.  The blog is hosted under the StackExchange network, and the graphic designer for StackExchange is expected to produce a blog theme in a few weeks.  Until then, the site will look sketchy, and we are still getting things up and running.  For example, the blog cannot process LaTeX yet, which limits our ability to publish technical posts.  I imagine we can get that resolved soon.

Our initial objective is to put out one to two posts per week: one post that is more “meaty,” by a contributor (i.e., not Joe or me!) that discusses a topic in some depth; and one post that is a review of activity on cstheory this week.  (Examples: these are the unanswered questions of the week; these are the editors’ choice of the most interesting answers to questions this week.)  We currently have commitments from four people to contribute to the blog, and we are actively looking for more participation.  Please email Joe or me, or add your name to the blog contributor  signup sheet, if you would like to be involved.  We would like to host expository material in all areas of theoretical computer science, and also more specialized discussions, that would primarily interest experienced researchers.

Edit: Math is now rendering; we appear ready to go.

“Editor’s Selection”

My post from yesterday on the Church-Turing Thesis now bears a green-and-white checkbox icon labeled “Editor’s Selection.”  This is because yesterday afternoon, an editor of ResearchBlogging.org selected it (and two other posts, by different bloggers) as “interesting and notable ResearchBlogging.org posts in the physical sciences, chemistry, engineering, computer science, geosciences and mathematics” for this week.

I have no idea what the “acceptance rate percentage” is for this, but I figured I should explain what the icon was doing there.  I wrote one previous post about ResearchBlogging.org, when I first joined.

A mathematical proof of the Church-Turing Thesis?

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.