Church-Turingova teza odnosi se na koncept učinkovite, sustavne ili mehaničke metode u logici, matematici i informatici. Formulira se kao opis intuitivnog koncepta izračunljivosti i, u odnosu na opće rekurzivne funkcije, češće se naziva Churchovom tezom. Također se odnosi na teoriju računalno računalnih funkcija. Teza se pojavila 1930-ih, kada sama računala još nisu postojala. Kasnije je dobio ime po američkom matematičaru Alonsu Churchu i njegovom britanskom kolegi Alanu Turingu.
Učinkovitost metode za postizanje rezultata
Prvi uređaj koji je nalikovao modernom računalu bio je Bombie, stroj koji je stvorio engleski matematičar Alan Turing. Koristio se za dešifriranje njemačkih poruka tijekom Drugog svjetskog rata. Ali za svoju tezu i formalizaciju koncepta algoritma koristio je apstraktne strojeve, kasnije nazvane Turingovi strojevi. Teza predstavljainteres i za matematičare i za programere, budući da je ova ideja inspirirala kreatore prvih računala.
U teoriji izračunljivosti, Church-Turingova teza poznata je i kao pretpostavka o prirodi izračunljivih funkcija. Navodi da za bilo koju algoritamski izračunljivu funkciju na prirodnim brojevima postoji Turingov stroj koji je sposoban izračunati. Ili, drugim riječima, postoji algoritam prikladan za to. Dobro poznati primjer učinkovitosti ove metode je test tablice istinitosti za testiranje tautologije.
Način postizanja bilo kojeg željenog rezultata naziva se "učinkovit", "sustavni" ili "mehanički" ako:
- Metoda je određena u smislu konačnog broja točnih instrukcija, svaka instrukcija je izražena korištenjem konačnog broja znakova.
- Radit će se bez pogrešaka, proizvesti ć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 domišljatost od strane osobe koja izvodi radnju
Ranije u matematici, neformalni izraz "učinkovito izračunljiv" korišten je 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 izračuna. Jedno od postignuća Alana Turinga bilo jeprikaz formalno točnog predikata, uz pomoć kojeg bi bilo moguće zamijeniti neformalni, ako se koristi uvjet učinkovitosti metode. Crkva je došla do istog otkrića.
Osnovni koncepti rekurzivnih funkcija
Turingova promjena predikata na prvi je 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 odabire 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 učinkovitosti. Postojala je još jedna razlika između ta dva otkrića. Upravo je Church razmatrao samo primjere pozitivnih cijelih brojeva, dok je Turing svoj rad opisao kao pokrivanje izračunljivih funkcija s integralnom ili realnom varijablom.
Uobičajene rekurzivne funkcije
Churchova izvorna formulacija navodi da se izračun može izvesti pomoću λ-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 stanične automate, kombinatore, strojeve za registraciju i sustave 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 u kojima je moguće više od jednog argumenata.
Izrada metodeλ-račun
Godine 1936. Alonso Church stvorio je metodu određivanja nazvanu λ-račun. Bio je povezan s prirodnim brojevima. Unutar λ-računa, znanstvenik je odredio njihovo kodiranje. Zbog toga se nazivaju crkvenim brojevima. Funkcija koja se temelji na prirodnim brojevima nazvana je λ-izračunljivom. Postojala je još jedna definicija. Funkcija iz Churchove teze naziva se λ-izračunljiva pod dva uvjeta. Prvi je zvučao ovako: ako je izračunat na elementima Crkve, a drugi uvjet je bila mogućnost da ga predstavlja član λ-računa.
Također 1936. godine, prije nego što je proučavao rad svog kolege, Turing je stvorio teorijski model za apstraktne strojeve koji su sada nazvani po njemu. Mogli su izvoditi izračune manipulirajući likovima na vrpci. To se također odnosi i na druge matematičke aktivnosti koje se nalaze u teorijskoj informatici, kao što je kvantno vjerojatnostno računanje. Funkcija iz Churchove teze tek je kasnije potkrijepljena Turingovim strojem. U početku su se oslanjali na λ-račun.
Izračunljivost funkcije
Kada su prirodni brojevi prikladno kodirani kao nizovi znakova, za funkciju na prirodnim brojevima se kaže da je Turing-izračunljiva ako je apstraktni stroj pronašao traženi algoritam i ispisao ovu funkciju na vrpcu. Takav uređaj, koji nije postojao 1930-ih, u budućnosti bi se smatrao računalom. Apstraktni Turingov stroj i Churchova teza najavili su eru razvojaračunalnih uređaja. Dokazano je da se klase funkcija koje su formalno definirala oba znanstvenika podudaraju. Stoga su kao rezultat obje izjave spojene u jednu. Računalne 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čna gledišta 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 zadanih su bile povezane s metodama građenja strojeva, kojih tada nije bilo. Da bismo dokazali Church-Turingovu tezu, polazi se od činjenice da je svaki realistični model računanja ekvivalentan.
Zbog raznolikosti različitih analiza, ovo se općenito smatra posebno jakim dokazom. Svi pokušaji preciznijeg definiranja intuitivnog pojma učinkovito izračunljive funkcije pokazali su se ekvivalentnim. Svaka predložena analiza pokazala je da izdvaja istu klasu funkcija, odnosno onih koje su izračunave Turingovim strojevima. No pokazalo se da su neki računski modeli učinkovitiji u smislu korištenja vremena i memorije za različite zadatke. Kasnije je zapaženo da su osnovni koncepti rekurzivnih funkcija i Churchova teza prilično hipotetski.
Teza M
Važno je razlikovati Turingovu tezu i tvrdnju da sve što se može izračunati računalnim uređajem može izračunati njegov stroj. Druga opcija ima svoju definiciju. Gandhi drugu rečenicu naziva "Teza M". To ide ovako: "Sve što se može izračunati pomoću uređaja može se izračunati Turingovim strojem." U užem smislu teze, radi se o empirijskoj tvrdnji čija je vrijednost istinitosti nepoznata. Turingova teza i "Teza M" ponekad se brkaju. Druga verzija je uglavnom netočna. Opisani su različiti uvjetni strojevi koji mogu računati funkcije koje nisu Turingove izračunljive. Važno je napomenuti da prva teza ne povlači za sobom drugu, ali je u skladu s njenom netočnosti.
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ćenitiju formulaciju. On je djelomično rekurzivne nazvao sve parcijalne funkcije koje se mogu izračunati algoritmima.
Obrnuta implikacija se obično naziva Churchovom obrnutom tezom. Ona leži u činjenici da se svaka rekurzivna funkcija pozitivnih cijelih brojeva učinkovito evaluira. U užem smislu teza jednostavno označava takvu mogućnost. A u širem smislu, apstrahira se od pitanja može li taj uvjetni stroj postojati u njemu.
Kvantna računala
Koncepti izračunljivih funkcija i Churchova teza postali su važno otkriće za matematiku, teoriju strojeva i mnoge druge znanosti. Ali tehnologija se mnogo promijenila i nastavlja se poboljšavati. Pretpostavlja se da kvantna računala mogu obavljati mnoge uobičajene zadatke s manje vremena od modernih. Ali pitanja ostaju, kao što je problem zaustavljanja. Kvantno računalo ne može odgovoriti na to. A, prema Church-Turing tezi, niti jedan drugi računalni uređaj.
