Strong Church Turing thesis

Written by Jaime Sevilla Molina, Eric B, et al. last updated

Summaries

There are no custom summaries written for this page, so users will see an excerpt from the beginning of the page when hovering over links to this page. You can create up to 3 custom summaries; by default you should avoid creating more than one summary unless the subject matter benefits substantially from multiple kinds of explanation.

Every realistic model of computation is polynomial time reducible to probabilistic Turing machines

Which amounts to saying that every computable process in the universe can be efficiently simulated by a probabilistic Turing machine.

The definition of realistic model appeals to intuition rather than a precise definition of realistic. A rule of thumb is that a computation model is realistic if it could be used to accurately model some physical process. For example, there is a clear relation between the model of register machines and the inner workings of personal computers. On the other hand, a computational model which can access an NP oracle does not have a physical counterpart.

As it happened with the standard Church-Turing thesis, this is an inductive rather than a mathematically defined statement. However, unlike the standard CT thesis, it is widely believed to be wrong, primarily because quantum computation stands as a highly likely counterexample to the thesis.

We remark that non-deterministic computation is not a candidate counterexample to the strong CT thesis, since it is not realistic. That said, we can find a relation between the two concepts: if and then , so quantum computation can be efficiently simulated, and we lose the strongest contestant for a counterexample to Strong CT.

Consequences of falsehood

The falsehood of the Strong CT thesis opens up the possibility of the existence of physical processes that, while computable, cannot be modeled in a reasonable time with a classical computer. One consequence of this, that would also mean that if quantum computing is possible the speed .up it provides is non-trivial.

Epistemic processes which assign priors using a penalty for computational time complexity are misguided if the Strong CT thesis is false. See for example Levin search.