Jedno od centralnih pitanja teorijske informatike jeste pitanje šta znači da je neki problem algoritamski rešiv. Čerč–Tjuringova teza daje odgovor na ovo pitanje povezivanjem intuitivnog pojma algoritma sa formalnim matematičkim modelima izračunavanja.
Iako se često pogrešno smatra matematičkom teoremom, Čerč–Tjuringova teza predstavlja filozofsku i metodološku tvrdnju o prirodi izračunljivosti.
Tridesetih godina XX veka, Alonzo Čerč i Alan Tjuring nezavisno su razvili formalne modele izračunavanja. Čerč je predložio λ-račun, dok je Tjuring uveo apstraktni model poznat kao Tjuringova mašina.
Uprkos različitim formalizmima, pokazano je da oba modela opisuju istu klasu funkcija, što je dovelo do opšte prihvaćenog stava da oni precizno opisuju pojam algoritma.
| Pojam | Objašnjenje |
|---|---|
| Tjuringova mašina | Apstraktni model računara sa beskonačnom trakom |
| Algoritam | Konačan niz precizno definisanih koraka |
| Izračunljivost | Mogućnost rešavanja problema algoritmom |
Iako Čerč–Tjuringova teza formalizuje pojam izračunavanja, ona istovremeno ukazuje na postojanje problema koji se ne mogu rešiti algoritamski. Najpoznatiji takav problem je problem zaustavljanja.
Ovaj rezultat ima duboke posledice, jer pokazuje da postoje fundamentalna ograničenja nezavisna od tehnološkog napretka.
