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 [4bd $~$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].

[todo: 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.] [comment: probably not worth raising? human brains have crazy-low decoherence times.]