Church-Turingova teza odnosi se na koncept efikasne, sistematske ili mehaničke metode u logici, matematici i informatici. Formulisan je kao opis intuitivnog koncepta izračunljivosti i, u odnosu na opšte rekurzivne funkcije, češće se naziva Churchovom tezom. Takođe se odnosi na teoriju kompjuterski izračunljivih funkcija. Teza se pojavila 1930-ih, kada sami kompjuteri još nisu postojali. Kasnije je dobio ime po američkom matematičaru Alonsu Churchu i njegovom britanskom kolegi Alanu Turingu.
Efikasnost metode za postizanje rezultata
Prvi uređaj koji je ličio na moderan kompjuter bio je Bombie, mašina koju je kreirao engleski matematičar Alan Turing. Korišćen je za dešifrovanje nemačkih poruka tokom Drugog svetskog rata. Ali za svoju tezu i formalizaciju koncepta algoritma koristio je apstraktne mašine, kasnije nazvane Turingove mašine. Thesis presentsinteresovanje i za matematičare i za programere, jer je ova ideja inspirisala kreatore prvih kompjutera.
U teoriji izračunljivosti, Church-Turingova teza je također poznata kao pretpostavka o prirodi izračunljivih funkcija. Navodi da za bilo koju algoritamski izračunljivu funkciju na prirodnim brojevima postoji Turingova mašina sposobna da je izračuna. Ili, drugim riječima, postoji odgovarajući algoritam za to. Dobro poznati primjer efikasnosti ove metode je test tabele istinitosti za testiranje tautologije.
Način za postizanje bilo kojeg željenog rezultata naziva se "efikasan", "sistematski" ili "mehanički" ako:
- Metoda je specificirana u smislu konačnog broja tačnih instrukcija, svaka instrukcija je izražena korištenjem konačnog broja znakova.
- Radit će bez grešaka, proizvešće željeni rezultat u određenom broju koraka.
- Ovu metodu može izvesti čovjek bez pomoći bilo kakvom opremom osim papira i olovke
- Ne zahtijeva razumijevanje, intuiciju ili genijalnost od strane osobe koja izvodi radnju
Ranije u matematici, neformalni termin "efikasno izračunljiv" se koristio za označavanje funkcija koje se mogu izračunati olovkom i papirom. Ali sam pojam algoritamske izračunljivosti bio je intuitivniji od bilo čega konkretnog. Sada ga je karakterizirala funkcija s prirodnim argumentom, za koju postoji algoritam proračuna. Jedno od dostignuća Alana Turinga jepredstavljanje formalno egzaktnog predikata, uz pomoć kojeg bi bilo moguće zamijeniti neformalni, ako se koristi uslov efikasnosti metode. Crkva je došla do istog otkrića.
Osnovni koncepti rekurzivnih funkcija
Turingova promjena predikata je na prvi pogled izgledala drugačije od one koju je predložio njegov kolega. Ali kao rezultat toga, ispostavilo se da su ekvivalentni, u smislu da svaki od njih bira isti skup matematičkih funkcija. Church-Turingova teza je tvrdnja da ovaj skup sadrži svaku funkciju čije se vrijednosti mogu dobiti metodom koja zadovoljava uvjete efikasnosti. Postojala je još jedna razlika između ova dva otkrića. Church je razmatrao samo primjere pozitivnih cijelih brojeva, dok je Turing opisao svoj rad kao pokrivanje izračunljivih funkcija integralnom ili realnom varijablom.
Uobičajene rekurzivne funkcije
Churchova originalna formulacija kaže da se proračun može obaviti korištenjem λ-računa. Ovo je ekvivalentno korištenju generičkih rekurzivnih funkcija. Church-Turingova teza pokriva više vrsta računanja nego što se prvobitno mislilo. Na primjer, vezano za ćelijske automate, kombinatore, mašine za registraciju i sisteme zamjene. Godine 1933. matematičari Kurt Gödel i Jacques Herbrand stvorili su formalnu definiciju klase koja se naziva opće rekurzivne funkcije. Koristi funkcije gdje je moguće više od jednog argumenata.
Kreiranje metodeλ-račun
Godine 1936. Alonso Church je stvorio metodu određivanja nazvanu λ-račun. Bio je povezan sa prirodnim brojevima. Unutar λ-računa, naučnik je odredio njihovo kodiranje. Zbog toga se nazivaju crkvenim brojevima. Funkcija zasnovana na prirodnim brojevima nazvana je λ-izračunljiva. Postojala je još jedna definicija. Funkcija iz Churchove teze naziva se λ-izračunljiva pod dva uslova. Prvi je zvučao ovako: ako je izračunat na crkvenim elementima, a drugi uslov je bila mogućnost da bude predstavljen članom λ-računa.
Također 1936. godine, prije nego što je proučavao rad svog kolege, Turing je stvorio teorijski model za apstraktne mašine koje su sada nazvane po njemu. Mogli su da izvrše proračune manipulišući likovima na traci. Ovo se također odnosi i na druge matematičke aktivnosti koje se nalaze u teorijskoj informatici, kao što je kvantno vjerovatno računanje. Funkcija iz Churchove teze tek je kasnije potkrijepljena Turingovom mašinom. U početku su se oslanjali na λ-račun.
Proračunljivost funkcije
Kada su prirodni brojevi na odgovarajući način kodirani kao nizovi znakova, za funkciju na prirodnim brojevima se kaže da je izračunljiva po Tjuringu ako je apstraktna mašina pronašla traženi algoritam i odštampala ovu funkciju na traci. Takav uređaj, koji nije postojao 1930-ih, u budućnosti bi se smatrao kompjuterom. Apstraktna Turingova mašina i Churchova teza najavili su eru razvojaračunarskih uređaja. Dokazano je da se klase funkcija koje su formalno definisala oba naučnika poklapaju. Stoga su, kao rezultat, obje izjave spojene u jednu. Računske funkcije i Churchova teza također su imale snažan utjecaj na koncept izračunljivosti. Oni su također postali važan alat za matematičku logiku i teoriju dokaza.
Opravdanje i problemi metode
Postoje oprečni stavovi o tezi. Prikupljeni su brojni dokazi za "radnu hipotezu" koju su predložili Church i Turing 1936. godine. Ali sve poznate metode ili operacije za otkrivanje novih efektivno izračunljivih funkcija iz datih su bile povezane sa metodama izgradnje mašina koje tada nisu postojale. Da bi se dokazala Church-Turingova teza, polazi se od činjenice da je svaki realistički model izračunavanja ekvivalentan.
Zbog raznolikosti različitih analiza, ovo se općenito smatra posebno jakim dokazom. Svi pokušaji da se preciznije definiše intuitivni pojam efektivno izračunljive funkcije pokazali su se kao ekvivalentni. Svaka analiza koja je predložena pokazala je da izdvaja istu klasu funkcija, odnosno onih koje su izračunave Turingovim mašinama. Ali pokazalo se da su neki računarski modeli efikasniji u smislu upotrebe vremena i memorije za različite zadatke. Kasnije je zapaženo da su osnovni koncepti rekurzivnih funkcija i Churchova teza prilično hipotetički.
Thesis M
Važno je napraviti razliku između Turingove teze i tvrdnje da sve što se može izračunati pomoću računarskog uređaja može se izračunati njegovom mašinom. Druga opcija ima svoju definiciju. Gandhi drugu rečenicu naziva "Teza M". To ide ovako: "Šta god se može izračunati pomoću uređaja, može se izračunati pomoću Turingove mašine." U užem smislu teze, radi se o empirijskoj propoziciji čija je vrijednost istinitosti nepoznata. Turingova teza i "Teza M" se ponekad brkaju. Druga verzija je uglavnom netačna. Opisane su različite uslovne mašine koje mogu da računaju funkcije koje nisu Tjuringovo izračunave. Važno je napomenuti da prva teza ne povlači za sobom drugu, ali je u skladu sa njenom lažnošću.
Obrnuta implikacija teze
U teoriji izračunljivosti, Churchova teza se koristi kao opis pojma izračunljivosti pomoću klase općih rekurzivnih funkcija. Amerikanac Stephen Kleene dao je opštiju formulaciju. On je djelomično rekurzivne nazvao sve parcijalne funkcije izračunave algoritmima.
Obrnuta implikacija se obično naziva Churchovom obrnutom tezom. Ona leži u činjenici da se svaka rekurzivna funkcija pozitivnih cijelih brojeva efikasno procjenjuje. U užem smislu teza jednostavno označava takvu mogućnost. I u širem smislu, apstrahuje se od pitanja da li ova uslovna mašina može postojati u njoj.
Kvantni kompjuteri
Koncepti izračunljivih funkcija i Churchova teza postali su važno otkriće za matematiku, teoriju mašina i mnoge druge nauke. Ali tehnologija se dosta promijenila i nastavlja da se poboljšava. Pretpostavlja se da kvantni računari mogu obavljati mnoge uobičajene zadatke sa manje vremena od modernih. Ali pitanja ostaju, kao što je problem zaustavljanja. Kvantni kompjuter ne može odgovoriti na to. A, prema Church-Turing tezi, niti jedan drugi računarski uređaj.
