Church-Turingova teza se nanaša na koncept učinkovite, sistematične ali mehanske metode v logiki, matematiki in računalništvo. Formulira se kot opis intuitivnega koncepta izračunljivosti in se v zvezi s splošnimi rekurzivnimi funkcijami pogosteje imenuje Churcheva teza. Nanaša se tudi na teorijo računalniško izračunljivih funkcij. Teza se je pojavila v tridesetih letih prejšnjega stoletja, ko sami računalniki še niso obstajali. Kasneje je bil poimenovan po ameriškem matematiku Alonsu Churchu in njegovem britanskem kolegu Alanu Turingu.
Učinkovitost metode za doseganje rezultata
Prva naprava, ki je bila podobna sodobnemu računalniku, je bil Bombie, stroj, ki ga je ustvaril angleški matematik Alan Turing. Uporabljali so ga za dešifriranje nemških sporočil med drugo svetovno vojno. Toda za svojo tezo in formalizacijo koncepta algoritma je uporabil abstraktne stroje, kasneje imenovane Turingove stroje. Diplomsko delo predstavljazanimanje tako za matematike kot programerje, saj je ta ideja navdihnila ustvarjalce prvih računalnikov.
V teoriji izračunljivosti je Church-Turingova teza znana tudi kot domneva o naravi izračunljivih funkcij. Navaja, da za vsako algoritemsko izračunljivo funkcijo na naravnih številih obstaja Turingov stroj, ki jo je sposoben izračunati. Ali, z drugimi besedami, obstaja algoritem, primeren za to. Dobro znan primer učinkovitosti te metode je test tabele resnice za testiranje tavtologije.
Način za doseganje želenega rezultata se imenuje "učinkovit", "sistematičen" ali "mehanski", če:
- Metoda je določena v smislu končnega števila natančnih navodil, vsako navodilo je izraženo s končnim številom znakov.
- Potekal bo brez napak, dal bo želeni rezultat v določenem številu korakov.
- Metodo lahko izvede človek brez pomoči s katero koli opremo, razen s papirjem in svinčnikom
- Ne zahteva razumevanja, intuicije ali iznajdljivosti s strani osebe, ki izvaja dejanje
Prej v matematiki je bil neformalni izraz "učinkovito izračunljiv" uporabljen za sklicevanje na funkcije, ki jih je mogoče izračunati s svinčnikom in papirjem. Toda sam pojem algoritemske izračunljivosti je bil bolj intuitiven kot karkoli konkretnega. Zdaj je bila značilna funkcija z naravnim argumentom, za katero obstaja algoritem za izračun. Eden od dosežkov Alana Turinga je bilpredstavitev formalno natančnega predikata, s pomočjo katerega bi bilo mogoče zamenjati neformalnega, če uporabimo pogoj učinkovitosti metode. Cerkev je odkrila enako.
Osnovni koncepti rekurzivnih funkcij
Turingova sprememba predikatov je bila na prvi pogled videti drugačna od tiste, ki jo je predlagal njegov kolega. Toda posledično so se izkazali za enakovredne, v smislu, da vsak od njih izbere isti niz matematičnih funkcij. Church-Turingova teza je trditev, da ta niz vsebuje vsako funkcijo, katere vrednosti je mogoče dobiti z metodo, ki izpolnjuje pogoje učinkovitosti. Med obema odkritjema je bila še ena razlika. Church je upošteval le primere pozitivnih celih števil, Turing pa je svoje delo opisal kot pokrivanje izračunljivih funkcij z integralno ali realno spremenljivko.
običajne rekurzivne funkcije
Churchova izvirna formulacija navaja, da je izračun mogoče izvesti z uporabo λ-računa. To je enakovredno uporabi generičnih rekurzivnih funkcij. Church-Turingova teza zajema več vrst računanja, kot se je prvotno mislilo. Na primer v zvezi s celičnimi avtomati, kombinatorji, registracijskimi stroji in nadomestnimi sistemi. Leta 1933 sta matematika Kurt Gödel in Jacques Herbrand ustvarila formalno definicijo razreda, imenovanega splošne rekurzivne funkcije. Uporablja funkcije, kjer je možnih več kot en argument.
Ustvarjanje metodeλ-račun
Leta 1936 je Alonso Church ustvaril metodo določanja, imenovano λ-račun. Povezan je bil z naravnimi števili. Znotraj λ-računa je znanstvenik določil njihovo kodiranje. Posledično se imenujejo cerkvene številke. Funkcija, ki temelji na naravnih številih, je bila imenovana λ-izračunljiva. Obstajala je še ena definicija. Funkcija iz Churchove teze se imenuje λ-izračunljiva pod dvema pogojema. Prvi je zvenel takole: če je bil izračunan na cerkvenih elementih, drugi pogoj pa je bila možnost, da ga predstavlja član λ-računa.
Turing je leta 1936, preden je preučeval delo svojega kolega, ustvaril teoretični model za abstraktne stroje, ki se zdaj imenujejo po njem. Lahko bi izvajali izračune z manipuliranjem znakov na traku. To velja tudi za druge matematične dejavnosti, ki jih najdemo v teoretični računalniški znanosti, kot je kvantno verjetnostno računanje. Funkcija iz Churchove teze je bila šele kasneje utemeljena s Turingovim strojem. Sprva so se zanašali na λ-račun.
Izračunljivost funkcije
Ko so naravna števila ustrezno kodirana kot zaporedja znakov, se za funkcijo na naravnih številih reče, da je Turingovo izračunljiva, če je abstraktni stroj našel zahtevani algoritem in to funkcijo natisnil na trak. Takšna naprava, ki v tridesetih letih prejšnjega stoletja ni obstajala, bi v prihodnosti veljala za računalnik. Abstraktni Turingov stroj in Churcheva teza sta naznanila obdobje razvojaračunalniške naprave. Dokazano je bilo, da se razreda funkcij, ki sta jih formalno opredelila oba znanstvenika, sovpadata. Zato sta bili obe izjavi združeni v eno. Računske funkcije in Churcheva teza so prav tako močno vplivale na koncept izračunljivosti. Postali so tudi pomembno orodje za matematično logiko in teorijo dokazov.
Utemeljitev in težave metode
Obstajajo nasprotujoči si pogledi na tezo. Za "delovno hipotezo", ki sta jo leta 1936 predlagala Church in Turing, so bili zbrani številni dokazi. Toda vse znane metode oziroma operacije za odkrivanje novih učinkovito izračunljivih funkcij iz danih so bile povezane z metodami gradnje strojev, ki jih takrat še ni bilo. Da bi dokazali Church-Turingovo tezo, izhajamo iz dejstva, da je vsak realističen model računanja enak.
Zaradi različnih analiz se to na splošno šteje za posebej močan dokaz. Vsi poskusi natančnejše opredelitve intuitivnega pojma učinkovito izračunljive funkcije so se izkazali za enakovredne. Vsaka predlagana analiza se je izkazala za isti razred funkcij, in sicer tiste, ki jih je mogoče izračunati s Turingovimi stroji. Toda nekateri računalniški modeli so se izkazali za učinkovitejše v smislu porabe časa in pomnilnika za različne naloge. Kasneje je bilo ugotovljeno, da so osnovni koncepti rekurzivnih funkcij in Churcheva teza precej hipotetični.
Diplomsko delo M
Pomembno je razlikovati med Turingovo tezo in trditvijo, da vse, kar je mogoče izračunati z računalniško napravo, lahko izračuna njen stroj. Druga možnost ima svojo definicijo. Gandhi drugi stavek imenuje "Teza M". Gre takole: "Karkoli lahko izračuna naprava, lahko izračuna Turingov stroj." V ožjem pomenu teze gre za empirično trditev, katere resnična vrednost ni znana. Turingova teza in "teza M" se včasih zamenjujeta. Druga različica je na splošno napačna. Opisani so bili različni pogojni stroji, ki lahko izračunajo funkcije, ki niso Turingovo izračunljive. Pomembno je omeniti, da prva teza ne vključuje druge, ampak je skladna s svojo napačnostjo.
Obratna implikacija teze
V teoriji izračunljivosti se Churcheva teza uporablja kot opis pojma izračunljivosti z razredom splošnih rekurzivnih funkcij. Američan Stephen Kleene je dal bolj splošno formulacijo. Delno rekurzivne je imenoval vse delne funkcije, ki jih je mogoče izračunati z algoritmi.
Obratna implikacija se običajno imenuje Churchjeva obratna teza. Leži v tem, da se vsaka rekurzivna funkcija pozitivnih celih števil učinkovito ovrednoti. V ožjem pomenu teza preprosto označuje takšno možnost. In v širšem smislu, abstrahira od vprašanja, ali lahko ta pogojni stroj obstaja v njem.
Kvantni računalniki
Koncepti izračunljivih funkcij in Churcheva teza so postali pomembno odkritje za matematiko, teorijo strojev in številne druge znanosti. Toda tehnologija se je zelo spremenila in se še izboljšuje. Domneva se, da lahko kvantni računalniki opravljajo številne običajne naloge z manj časa kot sodobni. Toda vprašanja ostajajo, kot je problem ustavljanja. Kvantni računalnik nanj ne more odgovoriti. In v skladu s Church-Turingovo tezo tudi nobena druga računalniška naprava.
