Istnieją jeszcze inne wersje definiujące hipotezę. Przykładowa, fizyczna hipoteza Churcha-Turinga (ang. Physical Church-Turing Thesis, PCTT): Każdy problem, który jest fizycznie obliczalny, może być rozwiązany na maszynie Turinga.
Kolejną odmianą jest silna hipoteza Churcha-Turinga. Została ona wypracowana dużo później, w wyniku prac nad teorią złożoności. Każdy „rozsądny” model obliczeń może być efektywnie zasymulowany na .
Słowo „efektywny” oznacza tutaj istnienie redukcji problemów wykonywanych w czasie wielomianowym, stąd ta wersja definicji mówi, że wszystkie „rozsądne” modele obliczeń generują tę samą klasę problemów możliwych do policzenia w czasie wielomianowym. Zakładając, że przypuszczalna równość między probabilistycznym czasem wielomianowym równa jest deterministycznemu czasowi wielomianowemu, słowo „probabilistyczny” można w tej definicji pominąć.
Jeśli komputer kwantowy rzeczywiście jest możliwy do zbudowania, może to oznaczać obalenie silnej hipotezy Churcha-Turinga, ponieważ klasa problemów rozwiązywalnych w kwantowym czasie wielomianowym jest przypuszczalnie większa od probabilistycznego. Istnieją bowiem efektywne algorytmy kwantowe rozwiązujące problemy, dla których nie znamy efektywnych algorytmów probabilistycznych, np.