Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
There has been a great deal of discussion toward derandomization or taking out the random components of random algorithms. For example see ( )I once asked the question to Lance Fortnow at midwest theory about dequantization and that was meaningless. But it did spark a good discussion here see ( )But there are more fruitful avenues. A example of a weaker possibility that has something to do with quantum algorithms is given by Leslie Valiant Turing award winner 2011 ( ) . – Joshua Herman Jul 28 '11 at 12:55
@Joshua, the ACM has just posted Valiant's 2011 Turing Lecture (URL:… ); it's worth watching. For an applied perspective see recent JMR articles by Ilya Kuprov and collaborators: Polynomially scaling spin dynamics simulation algorithm based on adaptive state-space restriction and Polynomially scaling spin dynamics II: Further state-space compression using Krylov subspace techniques and zero track elimination. This slow converging of "pure" and "applied" CT/QIT is practically important & plenty of fun too. – John Sidles Aug 5 '11 at 18:37
up vote 38 down vote accepted

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 1043 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.

share|cite|improve this answer
Thanks very much, Scott! – Aaron Sterling Jul 29 '11 at 12:55
About "proof": I see the Dershowitz et al research program as trying to create a "ZF for algorithms," to axiomatize the intuitive notion of "algorithm." Then we can argue whether to include Choice or Determinacy, or the existence of a large cardinal -- whatever the computer science analogs of those things would be. I do believe that the way this axiomatization is being presented is results-driven ("look, we can prove this famous thesis"), but the authors of the CT-thesis paper do try to provide historical justification for their assumptions. – Aaron Sterling Jul 29 '11 at 13:02
@Scott Aaronson Interesting and illuminating view on QC. Just curious. What would it take to show QC cannot be a counterexample? – v s Jul 29 '11 at 14:35
You mean, to show QC is impossible? At the least, it would take a serious revision in our understanding of quantum mechanics. That could mean the discovery of some new physical theory that superseded QM (and so happened to restore BPP as the limit of computation), or some as-yet-undiscovered principle operating "on top of" or "alongside" QM that disallowed QC. Either way, Nobel prizes! :) – Scott Aaronson Jul 29 '11 at 14:45
another interesting quantum model between full quantum computation and classical is quantum discord based models, like DQC1. – Marcos Villagra Jul 29 '11 at 23:41

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.