Strong Church Turing thesis

Every re­al­is­tic model of com­pu­ta­tion is polyno­mial time re­ducible to prob­a­bil­is­tic Tur­ing machines

Which amounts to say­ing that ev­ery com­putable pro­cess in the uni­verse can be effi­ciently simu­lated by a prob­a­bil­is­tic Tur­ing ma­chine.

The defi­ni­tion of re­al­is­tic model ap­peals to in­tu­ition rather than a pre­cise defi­ni­tion of re­al­is­tic. A rule of thumb is that a com­pu­ta­tion model is re­al­is­tic if it could be used to ac­cu­rately model some phys­i­cal pro­cess. For ex­am­ple, there is a clear re­la­tion be­tween the model of reg­ister ma­chines and the in­ner work­ings of per­sonal com­put­ers. On the other hand, a com­pu­ta­tional model which can ac­cess an NP or­a­cle does not have a phys­i­cal coun­ter­part.

As it hap­pened with the stan­dard Church-Tur­ing the­sis, this is an in­duc­tive rather than a math­e­mat­i­cally defined state­ment. How­ever, un­like the stan­dard CT the­sis, it is widely be­lieved to be wrong, pri­mar­ily be­cause quan­tum com­pu­ta­tion stands as a highly likely coun­terex­am­ple to the the­sis.

We re­mark that non-de­ter­minis­tic com­pu­ta­tion is not a can­di­date coun­terex­am­ple to the strong CT the­sis, since it is not re­al­is­tic. That said, we can find a re­la­tion be­tween the two con­cepts: if \(P=NP\) and \(BQP\subset NP\) then \(BQP = P\), so quan­tum com­pu­ta­tion can be effi­ciently simu­lated, and we lose the strongest con­tes­tant for a coun­terex­am­ple to Strong CT.

Con­se­quences of falsehood

The false­hood of the Strong CT the­sis opens up the pos­si­bil­ity of the ex­is­tence of phys­i­cal pro­cesses that, while com­putable, can­not be mod­eled in a rea­son­able time with a clas­si­cal com­puter. One con­se­quence of this, that would also mean that if quan­tum com­put­ing is pos­si­ble the speed .up it pro­vides is non-triv­ial.

Epistemic pro­cesses which as­sign pri­ors us­ing a penalty for com­pu­ta­tional time com­plex­ity are mis­guided if the Strong CT the­sis is false. See for ex­am­ple Levin search.

show when QM is cov­ered?The failure of Strong CT raises the pos­si­bil­ity for hu­man minds in par­tic­u­lar, and gen­eral in­tel­li­gence in gen­eral be­ing im­pos­si­ble to simu­late with­out a quan­tum speedup, if it turns out that hu­man minds take ad­van­tage of quan­tum phe­nom­ena. We sus­pect, how­ever, that this is false. prob­a­bly not worth rais­ing? hu­man brains have crazy-low de­co­her­ence times.