Strong Church Turing thesis

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

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.