Problem (klasa pytań) jest rozstrzygalny wtedy i tylko wtedy, gdy istnieje metoda, która pozwala znaleźć pozytywną lub negatywną odpowiedź na każde pytanie z tej klasy. Metoda ta musi być efektywna.

Metoda efektywna powinna spełniać następujące warunki:

1. musi dać się jednoznacznie opisać za pomocą skończonego ciągu słów i/lub symboli, Metoda, której nie można w taki skończony sposób opisać, nie dałaby się przedstawić jako program dla jakiegokolwiek istniejącego lub tylko teoretycznie możliwego komputera (pewnego urządzenia technicznego).

2. jest metodą obliczania, Mówimy o metodzie efektywnej w wypadku poszukiwania odpowiedzi na drodze obliczania a nie np. eksperymentowania. Sprawdzanie za pomocą papierka lakmusowego, czy substancja jest kwasem nie jest typem metody, który mamy tu na uwadze. Stwierdzenie, że jest efektywna metoda uzyskania wyniku zwykle wypowiadane jest jako zdanie o istnieniu efektywnej metody uzyskania wartości takiej to a takiej funkcji matematycznej.

3. prowadzi do odpowiedzi, Metoda efektywna to metoda, postępowanie zgodnie z którą prowadzi do uzyskania odpowiedzi. Brak jakiejkolwiek odpowiedzi choćby tylko w wypadku jednej instancji dyskwalifikuje daną metodę jako metodę efektywną dla rozstrzygania danego problemu.

4. jej zastosowanie wymaga wykonania co najwyżej skończonej liczby operacji, kroków; Metoda efektywna to metoda, która w wypadku każdego pytania z klasy – dla której jest ona efektywna – składa się ze skończonej ilości operacji, kroków. Przy czym przez krok należy rozumieć jakieś proste, niezłożone postępowanie. Skończoność liczby kroków nie oznacza istnienia jakiejkolwiek bariery ich realizacji, np. fizycznej. Skończona liczba kroków to również taka liczba kroków, że ich wykonanie przekracza wszelkie możliwości fizyczne. Jest to skończoność liczbowa. Liczba może być skończona, choć dla jej zapisu nie starczyłoby materii wszechświata.

5. odpowiedź jest poprawna,

Odpowiedź otrzymana w wyniku zastosowania metody efektywnej musi być odpowiedzią poprawną, a więc być odpowiedzią pozytywną, gdy odpowiedź jest prawdziwa i być odpowiedzią negatywną, gdy odpowiedź jest fałszywa. Jeżeli prawdą jest, że α, to odpowiedź na pytanie, czy α powinna być TAK. Zaś gdy fałszem jest, że α odpowiedź winna być NIE.

6. stosuje się do wszystkich bez wyjątku instancji danego problemu,

Możliwość stosowania metody efektywnej do wszystkich instancji problemu oznacza, że nie stosuje się ona selektywnie.

7. daje się stosować precyzyjnie,

To, czy w danej sytuacji należy wykonać taki, czy też inny krok oraz wynik wykonania każdego kroku muszą być jednoznacznie określone przez metodę.

8. jeżeli istnieje potrzeba wykonania jakiegoś kroku, to krok ten daje się wykonać;

Wykonanie poszczególnego kroku nie podlega żadnym ograniczeniom. Jeżeli zastosowanie metody wymaga wykonania jakiegoś kroku, to nie może istnieć ograniczenie jakiejkolwiek natury uniemożliwiające jego wykonanie.

9. każdy krok jest �mechaniczny”,

�Mechaniczność” kroku oznacza, że jego wykonanie nie wymaga wiązania jakikolwiek treści z obiektami, na których jest wykonywana. �Mechaniczność” oznacza branie pod uwagę tylko �fizycznych” atrybutów obiektów, będących przedmiotem operacji. Jeżeli obiekty są napisami, to pod uwagę brane są ich budowa oraz kształty (wzorce). �Mechaniczność” metody oznacza, że jej stosowanie nie jest zależne od sposobu myślenia matematycznego tego, kto tę metodę stosuje. Tryb postępowania i wykonywania poszczególnych czynności jest niezależny od umiejętności matematycznych wykonawcy.

Metoda jest efektywna bez względu na to, czy jest ona komukolwiek znana i czy jest przez kogokolwiek stosowana.

Przed logikami stanęło trudne zadanie. Powiedzmy, że chcemy dowieść, że jakiś problem nie jest rozstrzygalny. Aby dowieść nierozstrzygalności, trzeba dowieść, że nie istnieje stosowna efektywna procedura �mechaniczna”. Z kolei jest to możliwe tylko wówczas, gdy pojęcie efektywnej procedury �mechanicznej” ma sens matematyczny. Zadania nadania sensu matematycznego intuicyjnie rozumianej efektywnej procedury �mechanicznej” skutecznie podjął się Turing, który tworząc maszynę (Turinga) potraktował dosłownie określenie �mechaniczna”. Przyjął, że procedura jest mechaniczna wtedy i tylko wtedy, gdy może zrealizować ją opisana przez niego jako teoretyczny twór maszyna (później nazwana maszyną Turinga).

Niezależnie od Turinga �mechaniczność” definiuje Church. W jego wypadku �mechaniczne” to tyle, co dające się opisać za pomocą (ogólnej) funkcji rekurencyjnej.

Szybko okazało się, że – choć na pierwszy rzut oka różne – koncepcje �mechaniczności” Turinga i Churcha – jeśli ograniczyć się do funkcji określonych na liczbach całkowitych dodatnich – są sobie równoważne.

Church formułuje swoją tezę w związku z uwagą Posta, że identyfikacja efektywnej obliczalności z rekurencją jest �hipotezą roboczą”. Church proponuje tezę: funkcja określona na liczbach całkowitych dodatnich jest obliczalna, jeśli jest rekurencyjna. Implikacja do niej odwrotna, że każda funkcja rekurencyjna określona na liczbach całkowitych dodatnich jest efektywnie obliczalna, powszechnie określana jest jako odwrotna teza Churcha (sam Church nie dokonywał takiego odróżnienia).

Teza Churcha-Turinga głosi, że intuicyjne pojęcie efektywnej procedury �mechanicznej” wyczerpuje się w pojęciu maszyny Turinga lub/i funkcji rekurencyjnej. Inaczej mówiąc, teza Churcha-Turinga stwierdza, że pojęcie funkcji obliczalnej wyczerpuje intuicyjną treść pojęcia metody efektywnej. Teza ta nie może zostać dowiedziona. Obalenie jej jest jednak możliwe, gdyby okazało się, że istnieje efektywna procedura �mechniczna”, która nie daje się opisać za pomocą aparatury pojęciowej maszyny Turinga lub funkcji rekurencyjnych. Zaproponowano wiele definicji efektywnej procedury �mechanicznej”.