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 \(P=NP\) and \(BQP\subset NP\) 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 Levin search.

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.