Ordet 'effektivt' betyder her op til polynomialtidsreduktioner. Den stærke Church-Turing-tese postulerer da, at alle 'rimelige' beregnelighedsmodeller udtrykker den samme klasse af problemer, som kan beregnes i polynomiel tid.
<!-- The word 'efficiently' here means up to polynomial-time reductions. The Strong Church-Turing Thesis, then, posits that all 'reasonable' models of computation yield the same class of problems that can be computed in polynomial time. -->
Forudsat formodningen at probabilistisk polynomiel tid (BPP) er lig deterministisk polynomiel tid (P), er ordet 'probabilistisk' valgfrit i den stærke Church-Turing-tese.
Filosofi Datalogi Videnskab Matematik