Extended Church-Turing Thesis

Question

One of the most discussed questions on the site has been What it Would Mean to Disprove the Church-Turing Thesis. This is partly because Dershowitz and Gurevich published a proof of the Church-Turing Thesis is the Bulletin of Symbolic Logic in 2008. (I won't discuss that here, but for a link and extensive comments, please see the original question, or -- shameless self-promotion -- a blog entry I wrote.)

This question is about the Extended Church-Turing Thesis, which, as formulated by Ian Parberry, is:

Time on all "reasonable" machine models is related by a polynomial.

Thanks to Giorgio Marinelli, I learned that one of the co-authors of the previous paper, Dershowitz, and a PhD student of his, Falkovich, have published a proof of the Extended Church-Turing Thesis, which just appeared at the workshop Developments of Computational Models 2011.

I just printed out the paper this morning, and I have skimmed it, nothing more. The authors claim that Turing machines can simulate any sequential computational device with at most polynomial overhead. Quantum computation and large-scale parallel computation are explicitly not covered. My question relates to the following statement in the paper.

We have shown -- as has been conjectured and is widely believed -- that every effective implementation, regardless of what data structures it uses, can be simulated by a Turing machine, with at most polynomial overhead in time complexity.

So, my question: is this really "widely believed," even in the case of "truly" sequential computation with no randomization? What if things are random? Quantum computing would be a likely counterexample, if in fact it can be instantiated, but are there possibilities "weaker" than quantum that would be counterexamples as well?

Answer 1

Preparatory Rant

I've gotta tell you, I don't see how talking about "proofs" of the CT or ECT adds any light to this discussion. Such "proofs" tend to be exactly as good as the assumptions they rest on---in other words, as what they take words like "computation" or "efficient computation" to mean. So then why not proceed right away to a discussion of the assumptions, and dispense with the word "proof"?

That much was clear already with the original CT, but it's even clearer with ECT---since not only is the ECT "philosophically unprovable," but today it's widely believed to be false! To me, quantum computing is the huge, glaring counterexample that ought to be the starting point for any modern discussion about the ECT, not something shunted off to the side. Yet the paper by Dershowitz and Falkovich doesn't even touch on QC until the last paragraph:

The above result does not cover large-scale parallel computation, such as quantum computation, as it posits that there is a fixed bound on the degree of parallelism, with the number of critical terms fixed by the algorithm. The question of relatively [sic] complexity of parallel models will be pursued in the near future.

I found the above highly misleading: QC is not a "parallel model" in any conventional sense. In quantum mechanics, there's no direct communication between the "parallel processes"---only interference of amplitudes---but it's also easy to generate an exponential number of "parallel processes." (Indeed, one could think of every physical system in the universe as doing so as we speak!) In any case, whatever you think about the interpretation of quantum mechanics (or even its truth or falsehood), it's clear that it requires a separate discussion!

Now, on to your (interesting) questions!

No, I don't know of any convincing counterexample to the ECT other than quantum computing. In other words, if quantum mechanics had been false (in a way that still kept the universe more "digital" than "analog" at the Planck scale---see below), then the ECT as I understand it still wouldn't be "provable" (since it would still depend on empirical facts about what's efficiently computable in the physical world), but it would be a good working hypothesis.

Randomization probably doesn't challenge the ECT as it's conventionally understood, because of the strong evidence today that P=BPP. (Though note that, if you're interested in settings other than language decision problems---for example, relational problems, decision trees, or communication complexity---then randomization provably can make a huge difference. And those settings are perfectly reasonable ones to talk about; they're just not the ones people typically have in mind when they discuss the ECT.)

The other class of "counterexamples" to the ECT that's often brought up involves analog or "hyper" computing. My own view is that, on our best current understanding of physics, analog computing and hypercomputing cannot scale, and the reason why they can't, ironically, is quantum mechanics! In particular, while we don't yet have a quantum theory of gravity, what's known today suggests that there are fundamental obstacles to running more than about 10⁴³ computation steps per second, or resolving distances smaller than about 10^-33 cm.

Finally, if you want to assume out of discussion anything that might be a plausible or interesting challenge to the ECT, and only allow serial, discrete, deterministic computation, then I agree with Dershowitz and Falkovich that the ECT holds! :-) But even there, it's hard to imagine a "formal proof" increasing my confidence in that statement -- the real issue, again, is just what we take words like "serial", "discrete", and "deterministic" to mean.

As for your last question:

Quantum computing would be a likely counterexample, if in fact it can be instantiated, but are there possibilities "weaker" than quantum that would be counterexamples as well?

Today, there are lots of interesting examples of physical systems that seem able to implement some of quantum computing, but not all of it (yielding complexity classes that might be intermediate between BPP and BQP). Furthermore, many of these systems might be easier to realize than a full universal QC. See for example this paper by Bremner, Jozsa, and Shepherd, or this one by Arkhipov and myself.

Answer 2

This answer is intended as a supplement to Scott Aaronson's answer (with which I mainly agree).

From an engineering perspective, it is striking that the Dershowitz/Falkovich article uses the word "random" only in the sense of "random-access memory", and moreover, the article does not use the word "sample" (or any of its variants) at all. Rather, the focus of the Dershowitz/Falkovic analysis is exclusively restricted to the computation of numeric functions.

This limitation is striking because the great majority of modern STEM computational resources (I will venture to say) do not respect the restriction to numeric functions, but rather are devoted to generate samples from distributions (e.g., molecular dynamics, turbulent fluid flow, fracture propagation, noisy spin systems both classical and quantum, waves propagating through random media, etc.).

Thus, if the "Extended Church-Turing Thesis" (ECT) is to have substantial relevance to STEM calculations defined broadly, perhaps the exclusive restriction to numeric functions ought to be lifted, and a generalized statement of the ECT be given, that encompasses sampling computations (and their validation and verification).

Would this generalized-to-sampling version of the ECT still fall within the purview of TCS as traditionally conceived? The answer seemingly is "yes", per the TCS Stack Exchange FAQ:

We refer you to the description of ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) ... TCS covers a wide variety of topics including probabilistic computation ... Work in this field [TCS] is often distinguished by its emphasis on mathematical technique and rigor.

These considerations suggest, that to be relevant to practical STEM computations, analyses of the ECT ought to include explicit considerations of sampling validation and verification ... and we may reasonably anticipate that this extension of the ECT would be associated both to beautiful mathematical theorems and to stimulating physical insights.