Strong Church Turing thesis
Every realistic model of computation isto
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 ofand the inner workings of personal computers. On the other hand, a computational model which can access an 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 , primarily because 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 \(P=NP\) and then \(BQP = P\), 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.
show when QM is covered?The failure of Strong CT raises the possibility for human minds in particular, and general intelligence in general being impossible to simulate without a quantum speedup, if it turns out that human minds take advantage of quantum phenomena. We suspect, however, that this is false. probably not worth raising? human brains have crazy-low decoherence times.
- Church-Turing thesis
A thesis about computational models