Fraza „intuicyjnie uznany za obliczalny” uniemożliwia przeprowadzenie matematycznego dowodu tej hipotezy. Każda funkcja obliczalna jest rekurencyjnie obliczalna
Łatwo zauważyć, że teza odwrotna jest dobrze określonym twierdzeniem matematycznym: każda funkcja rekurencyjnie obliczalna jest równoważna pewnemu programowi dla maszyny Turinga, jest algorytmem o skończonej liczbie kroków złożonym z operacji elementarnie rekurencyjnie obliczalnych. Tak więc Teza Churcha jest próbą odwrócenia tego twierdzenia. Status tezy Churcha jest niejasny, gdyż w zależności od jej interpretacji można ją uważać, za definicję obliczalności, model obliczalności, hipotezę empiryczna itp. W każdym z tych przypadków konieczna jest jednak analiza odpowiednio: adekwatności definicji, sensowności modelu, braku kontrprzykładu. Można Tezę Churcha traktować jako przykład naukowo-filozoficznego zastosowania indukcji – z braku kontrprzykładów wyciągamy wniosek o prawdziwości Tezy Churcha.
Każdy nieinteraktywny program może być zredukowany do rozwiązującej go maszyny Turinga, a ta może być wyrażona w każdym zupełnym w sensie Turinga języku programowania. Dlatego równoważne sformułowanie tej hipotezy mówi, że każdy istniejący algorytm można wyrazić w każdym zupełnym języku programowania.