Čerč-Tjuringova teza

U teoriji izračunljivosti, Čerč-Tjuringova teza (takođe poznata kao Tjuring-Čerčova teza, Čerč-Tjuringove pretpostavke, Čerčova teza, Čerčova pretpostavka i Tjuringova teza) je hipoteza ("teza") o prirodi izračunljivih funkcija. Jednostavno rečeno, Čerč-Tjuringova teza glasi da je funkcija na prirodnim brojevima izračunljiva u neformalnom smislu (tj izračunljiva od strane ljudskog bića korišćenjem metoda olovke i papira, ignorišući ograničenja resursa) ako i samo ako je izračunljiva Tjuringovom mašinom. Teza je dobila ime po američkom matematičaru Alonzu Čerču i britanskom matematičaru Alanu Tjuringu.

Pre preciznog definisanja izračunljivih funkcija, matematičari često koriste neformalan termin efektivno izračunljiv da opišu funkcije koje su za izračunljive metodama papira i olovke-. 1930-ih, bilo je nekoliko nezavisnih pokušaja da se formalizuje pojam Izračunljivosti:

• 1933, Austrijski-Američki matematičar Kurt Gedel, sa Žakom Erbranom, je napravio dormalnu definiciju klasa pod nazivom opšta rekurzivna funkcija. Klasa opštih rekurzivnih funkcija je najmanja klasa funkcija (moguće sa više od jednog argumenta) koja uključuje konstantne funkcije, projekte, funkciju naslednog, i koji je zatvoren u složenoj funkciji i rekurziji.
• 1936, Alonzo Čerč je stvorio metod za definisanje funkcija pod nazivom Lambda račun. U okviru lambda računa on je definisao kodiranje prirodnih brojeva pod nazivom Čerčovi brojevi. Funkcija nad prirodnim brojevima se zove lambda izračunljiva ako se odgovarajuća funkcija na Čerčovim brojevima može predstaviti u tajanju lambda računa.
• Takođe 1936, pre proučavanja Čerčovog rada, Alan Tjuring je stvorio teoretski model za mašine, koji se sada zove Tjuringove mašine, koje se mogu pobrinuti za računanje iz ulaza manipulacijom simbola na traci. S obzirom na odgovarajuće kodiranje prirodnih brojeva kao sekvence simbola, funkcija prirodnih brojeva  se naziva Tjuring izračunljiva ako neke Tjuringove mašine izračunaju odgovarajuću funkciju nad kodiranim prirodnim brojevima.

Čerč i Tjuring su dokazali da se ove tri formalno definisane klase izračunljivih funkcija poklapaju: funkcija je lambda izračuljiva  ako i samo ako je Tjuring izračunljiva i akko je opšte rekurzivna. Ovo je nateralo matematičare i informatičare da poveruju da je koncept izračunljivosti tačno okarakterisan ovim troma ekvivalentnim procesima. Ostali formalni pokušaji da se karakteriše izračunljivost je kasnije ojačao snagu ovog verovanja (pogledati ispod).

S druge strane, Čerč-Tjuringova teza navodi da su gorenavedene tri formalno definisane klase izračinljivih funkcija poklapaju sa neformalnom pojmom efikasno proračunljive funkcije. Pošto, kao neformalni pojam, koncept efektivne predvidivosti nema formalnu definiciju, teza, iako ima skoro univerzalnu prihvaćenost, ne može biti formalno dokazana.

Od svog osnivanja, varijacije na osnovnoj tezi su se pojavile, uključujući izjave o tome šta će moći fizički biti realizovano uz pomoć računara u našem univerzumu (fizička Čerč-Tjuring teza) i šta će moći biti efikasno izračunato (Složenost-teorijski Čerč-Tjuringova teza). Ove varijacije nisu zbog Čerča ili Tjuringa, ali proističu iz kasnijeg rada u teoriji složenosti i digitalne fizike. Teza ima implikacije za filozofiju duha.

Iskazi u Čerčovim i Tjuringovim rečima

Dž. B. Roser (1939) bavi se pojmom "efektivne izračunljivosti" na sledeći način: "Jasno postojanje CC i RC (Čerčovi je i Roserovi dokazi) pretpostavlja preciznu definiciju 'efektivnog' 'Efektivni metod" se ovde koristi u veoma posebnom smislu metode svi koraci koji su precizno unapred određeni i koji sigurno proizvede odgovor u konačnom broju koraka. „Takose prilog-pridev "efektivan"  koristi u smislu "1A: proizvodeći odlučujućeg, ubedljivog, ili željenog efekta" i "sposoban da proizvede rezultat".

U nastavku, reči "efikasno izračunljiv" će značiti "proizveden od strane bilo kog intuitivnog 'efektivnog' znači uopšte" i "efektivno podložan računanju" će značiti "proizvedeni od strane Tjuringove-mašine ili ekvivalentnog mehaničkog uređaja". Tjuringova "definicija" data u fusnoti u svojoj 1939. doktorirao tezu Sistemi logike baziranih na rednim brojevima pod nadzorom Čerča, su gotovo isti:

"† Mi ćemo koristiti izraz" izračunljiva funkcija ' da označimo funkciju izračunatu na mašini, i pustimo ' efektivno izračunate 'da se odnosi na intuitivnu ideju bez posebne  identifikacije sa bilo kojim od ovih definicija. "

Teza može glasiti kao sledeće:

Svaka efektivno izračunljiva funkcija je funkcija podležna računanju.

Tjuring je to izjavio na ovaj način:

"Konstatovano je da je ..." funkcija je efektivno izračunljiva ako se njene vrednosti mogu naći pomoću nekog čisto mehaničkog procesa. " Možemo uzeti doslovno, shvatajući da je čisto mehanički proces onaj koji može da se obavlja pomoću mašine ... dovodi do ... identifikacije izračunljivosti † sa efektivnom predvidivošču. "(† je fusnota iznad, Ibid.)

Istorija

Jedan od važnih problema za logičare 1930. bio je David Hilbertov Entscheidungsproblem, koja je zatražila da li je mehanički postupak za odvajanje matematičkih istina od matematičkih neistina. Ovoj potrazi je potrebno da  pojam "algoritma" ili "efektivne predvidivost" budu prikovani, barem dovoljno dobro za traganje za početak. Ali od samog početka pokušaja Alonza Čerča je počela sa debatom koja se nastavlja do današnjeg dana. Da li je pojam "efektivne predvidivost" da bude (i) "aksiom ili aksiomi" u aksiomatskog sistemu, ili (ii) samo definicija da je "identifikovao" dva ili više predloga, ili (iii) empirijska hipoteza da se utvrdi posmatranjem prirodnih događaja, ili (iv) ili samo predlog zarad argumenta (odnosno "teza").

Period 1930—1952.

U toku studiranja problema, Čerč i njegov student Stiven Klini uveo je pojam λ definisane funkcije, i oni su bili u stanju da dokažu da se nekoliko velikih klasa funkcija često sreću u teoriji brojeva λ-definisani. Rasprava je počela kada je Čerč predložio da Gedel treba definisati "efektivno izračunljive" funkcije kao λ definisane funkcije. Gedel, međutim, nije bio ubeđen i nazvao predlog "temeljno ne zadovoljava". Umesto toga, u prepisci sa Čerčom (ca 1934-5), Gedel je predložio akiomatizing pojam "efektivne predvidivosti"; Zaista, 1935 u pismu Klinu, Čerč je izvestio da:

"Njegova [Gedelov] jedina ideja u to vreme bila je da bi to bilo moguće, u smislu efikasne predvidivost kao nedefinisanog pojma, da navede skup aksioma koji bi otelovljavali opšteprihvaćena svojstva ovog pojma, i da uradi nešto na toj osnovi ".

Ali Gedel nije ponudio dalja uputstva. Na kraju, on bi predložio svoju (primitivnu) rekurziju, modifikovanu od strane Herbranda sugestiju, koju je Gedel detaljisao u svojim predavanjima iz 1934 Prinston NJ(Klini i Roser prepisali su beleške). Ali "nije mislio da dve ideje mogu na zadovoljavajući način biti identifikovane " osim heuristički ".

Dalje, bilo je neophodno da se identifikuju i dokaže ekvivalentnost dva pojma efikasne predvidivost. Opremljen lambda-računom i "primitivnom" rekurzijom, Stiven Klini uz pomoć Čerča i Dž. B. Rosera proizvodi dokaze (1933, 1935) da pokaže da su dva računa ekvivalentna. Čerč naknadno izmenjuje svoje metode uključuju upotrebu Herbrand-Gedel rekurzije, a zatim je dokazao (1936) da je Entscheidungsproblem nerešiv: Ne postoji uopšten "efektivnan obračun" (metod, algoritam) koji može da odredi da li su ili ne formule u bilo kojoj rekurziji - ili lambda računu "važeće" (preciznije: nema metode da se pokaže da dobro formirana formula ima "normalnan oblik").

Mnogo godina kasnije, u pismu upućenom Dejvisu (ca 1965), Gedel bi priznao da je "on bio, u vreme ovih [1934] predavanja, uopšte ubeđen da njegov koncept rekurzije čini sve moguće rekurzije". Po 1963-4 Gedel bi odrekao Herbrand-Gedel rekurziju i λ-računicu u korist Tjuringove mašine kao definicije "algoritma" ili "mehaničkog postupka" ili "formalnog sistema".

Hipoteza koja je dovela do prirodnog zakona ?: Krajem 1936 Alan Tjuringov rad (takođe dokazuje da je Entscheidungsproblem nerešiv) je dosravljen usmeno, ali se još nije pojavio u štampi. S druge strane, Emil Postov rad 1936 se pojavio i bio sertifikovan nezavisno od rada Tjuringovog rada. Post se snažno ne slaže sa Čerčovom "identifikacijom" efektivne izračunljivosti sa λ-računom i rekurzijom, navodeći:

"Zapravo posao je već urađen od strane Čerča i drugih nosi ovu identifikaciju znatno izvan radne faze hipoteze. Ali da prikrije ovu identifikaciju pod definicijom ... zaslepljuje nas na potrebu njene neprekidne verifikacije."

Umesto toga, on smatra pojam "efektivne predvidivosti" kao samo "radna hipoteza" koja može da se dovede  indukcionim obrazloženjem do "prirodno pravo", pre nego "definiciju ili aksiom". Ovu ideju je "oštro" kritikovao Čerč.

Tako je Post u svom radu 1936 takođe diskontovao Kurt Gedelovu sugestiju Čerču 1934-5 da teza može biti izražena kao aksiom ili skup aksioma.

Tjuring dodaje još jednu definiciju, Roser izjednačava sve tri: U samo kratkom vremenu, Tjuringov rad 1936-37 "Na izračunljivim brojeva, sa primenom u Entscheidungsproblem" se pojavio. U njoj je naveo još jedan pojam "efektivne izračunljivosti" sa uvođenjem svojih A-mašina (sada poznate kao Tjuringova mašina - apstraktan računarski model). U dokazu-skici dodaje kao "Prilog" u svoj rad 1936-37 , Tjuring je pokazao da su se klase funkcija definisana λ-računom i Tjuringova mašina poklopile. Čerč je brzo prepoznao koliko je ubedljiva Tjuringova analiza. U svom pregledu Tjuringovog rada rekao je da je jasno da je Tjuringova ideja "identifikacija sa efikasnosti u običnom (ne eksplicitno definisanom) smislu evidentna odmah".

Za nekoliko godina (1939) Tjuring bi predložio, kao Čerč i Klini pre njega, da je njegova formalna definicija mehaničke izračunljivosti bio ispravan. Tako, 1939. godine, i Čerč (1934) i Tjuring (1939) su individualno predložili da njihovi "formalni sistemi" budu definicije "efektivne predvidivost"; niko nije uramio njihove izjave kao tezu.

Roser (1939) je formalno identifikovao tri pojma kao definicije:

"Sve tri definicije su ekvivalentne, tako da nije bitno koja se koristi."

Klini predlaže Čerčovu tezu : Ovo je ostavilo otvoren izraz jedne "teze" Kliniju. U svom radu 1943 Rekurzivni Predikati i kvantifikatori Klini je predložio svoju "TEZU I":

"Ova heuristička činjenica [opšte rekurzivne funkcije su efikasno izračunate] ... dovela je Čerča da navede sledeću tezu (22). Ista teza je sadržana u Tjuringovom opisu računskih mašina (23).

"TEZA I. Svaka efektivno izračunljiva funkcija (efektivno odlučiv predikat) je opšte rekurzivna [Klinijev kurziv]

"Od precizne matematičke definicije pojma efektivno izračunljive (efektivno odlučive) je hteo, možemo iskoristiti ovu tezu ... kao definiciju toga ..."

"(²²) reference Čerča 1936

"(²³) reference Tjuringa 1936–7

Klini ide u beleški da :

"... Ta teza ima karakter jedne hipoteze tačke naglašene od strane Posta i Čerča (24). Ako uzmemo u obzir i njegovu tezu obrnutog tvrđenja kao definiciju, onda je hipoteza je hipoteza o primeni matematičke teorije razvijena iz definicije. Za prihvatanje hipoteze, postoje, kao što smo predložili, prilično uverljivi razlozi. "

.. "(24) reference Posta1936 Postova i Čerčova formalna definicija u teoriji rednih brojeva, Fond, Matematika vol 28 (1936) pp.11-21 (vidi ref #2, Dejvis 1965: 286).

Klinijeva Čerč-Tjuringova Teza: Nekoliko godina kasnije (1952) Klini bi otvoreno imenovao, branio, i izražavao dve "teze", a zatim ih "identifikovao" (pokazao jednakost) upotrebom njegove Teoreme HHH:

"Heuristički dokazi i drugi razlozi doveli su Čerča 1936 da predloži sledeće teze.

TEZA I. Svaka efektivno izračunljiva funkcija (efektivno odlučiv predikat) je opšte rekurzivna.

Teorema HHH: "Sledeće klase parcijalnih funkcija su koekstenzivne, tj imaju iste članove: (a) parcijalne rekurzivne funkcije, (b) izračunljive funkcije ...". Tjuringova teza: "Tjuringova teza da svaka funkcija koju bi trebalo prirodno smatrati za izračunljivu je izračunljiva pod svojom definicijom, odnosno jedna od njegovih mašina, je ekvivalentna tezi Čerča od strane Teoreme HHH."

Kasniji razvoji

Pokušaj da se razume pojam "efektivne izračunljivosti" je bolje vodio Robin Gandi (Tjuringov učenik i prijatelj) 1980. da analizira proračun mašine (kao suprotnost ljudskoj-izračunljivosti postupilo od Tjuringove mašine). Gandijeva radoznalost u vezi, i analizi, "ćelijskog automata", "Konvejeve igre života", "paralelizma" i "kristalnog automata" ga je navelo da predloži četiri "principa (ili ograničenja) ... koja su tvrdio je, bilo koja mašina mora zadovoljiti. " Njegov najvažniji četvrti, "princip kauzaliteta" se zasniva na "konačnoj brzini prostiranja efekata i signala; savremena fizika odbacuje mogućnost trenutnog delovanja na daljinu". Od ovih principa i nekih dodatnih ograničenja- (1a) donja granica na linearnoj dimenziji bilo kog dela, (1b) gornja granica brzina rasprostiranja (brzina svetlosti), (2) diskretan napredak mašine, i (3) determinističko ponašanje-da proizvodi teoremu koja "Ono što se može izračunati pomoću uređaja zadovoljava principe 1-4 je izračunljivo.".

U kasnim 1990-im Vilfred Zig analizirao jnj Tjuringove i Gandijeve pojmove "efektivne predvidivost" sa namerom da "oštrenja neformalnog pojma, formulisanje njegove opšte karakteristike aksiomatski, i istraživanju aksiomatskog okvira". U svom radu 1997. i 2002. godine Zig predstavlja niz ograničenja na ponašanje jednog računala- "agent ljudskog računarstva koji nastavlja mehanički". Ova ograničenja svode na:

• "(B.1) (Konačnosti) Postoji fiksno ograničenje na broju simboličnih konfiguracija koje računalo može odmah prepoznati.
• "(B.2) (Konačnosti) Postoji fiksno ograničenje na broju unutrašnjih stanja koje mogu biti u računalu.
• "(L.1) (Lokalitet) Računar može promeniti samo elemente posmatrane simboličke konfiguracije.
• "(L.2) (Lokalitet) Računar može pomeriti pažnju sa jedne simboličke konfiguracije na drugu, ali nova posmatrana konfiguracija mora biti unutar ograničene udaljenosti od neposredne prethodno posmatrane konfiguracije.
• "(D) (Odlučnost) Neposredno prepoznatljiva (sub-) Konfiguracija odlučuje jednoznačno sledeći korak izračunavanja (i ID [trenutni opis])"; Drugačije rečeno: "unutrašnje stanje A računalo zajedno sa posmatranom konfiguracijom fiksira jedinstven sledeći korak računanja i sledeće unutrašnje stanje."

Pitanje ostaje u aktivnoj diskusiji u okviru akademske zajednice.

Teza kao definicija

Teza može da se posmatra kao ništa osim obične matematičke definicije. Komentari od Gedela na temu ukazuju na ovaj stav, npr "osnovna tačna definicija mehaničke izračunljivosti je utvrđena van svake sumnje od strane Tjuringa". Slučaj za gledanje teze kao ništa više od definicije je eksplicitno stvorio Robert I. Soare u kojoj se takođe tvrdi da nije ništa manje verovatno da će Tjuringova definicija biti tačna nego ipsilon-delta definicija neprekidne funkcije.

Uspeh teze

Ostali formalizmi (osim rekurzije je λ-račun, i Tjuringova mašina) su predloženi za opisivanje efikasne predvidivosti / izračunljivosti. Stiven Klini (1952) dodaje na listu funkcije "Procenjivi u sistem S1" Kurt Gedela 1936, i Emil Postovih (1943, 1946) "kanonskih [takođe zvane normalnim] sistema". U 1950. Hao Vang i Martin Dejvis u velikoj meri su pojednostavili model Tjuringove mašine sa jednom trakom (vidi post-Tjuringovu Mašine). Marvin Minski je proširio model na dve ili više trake i uveliko pojednostavljena traka u "gore-dole šalterima", koje su Melzak i Lambek dalje evoluirali u ono što je sada poznato kao model brojač mašine. U kasnim 1960-im i ranim 1970-im istraživači su proširili model brojač mašine u Registar mašinu, bliski rođak sa modernim pojmom računara. Ostali modeli uključuju Kombinacijsku logiku i Markov algoritme. Gurevič dodaje model Pokazivač mašine Kolmogorova i Uspenskog (1953, 1958) : "... oni su samo hteli da ... uvere sebe da ne postoji način da se produži pojam izračunljive funkcije."

Svi ovi doprinosi uključuju dokaze da su modeli su računski ekvivalentni Tjuringovoj mašini; takvi modeli su, kako je rečeno Tjuring potpuni. Zato što su svi ovi različiti pokušaji formalizovanja koncepta "efikasna predvidivost / izračunljivost" dale su ekvivalentne rezultate, sada se generalno pretpostavlja da je Čerč-Tjuringova teza tačna. U stvari, Gedel (1936) je predložio nešto jače od ovoga; on je primetio da postoji nešto "apsolutno" o konceptu "Procenjivi u S1":

"To može da se pokaže da je funkcija koja je izračunljiva ['Procenjiva'] u jednom od sistema Si, ili čak u sistemu transfinit tipa, već izračunljiva [Procenjiva] u S1. Tako je koncept" za izračunavanje "['Procenjivi '] u izvesnom smislu određenom' apsolutno ', dok su praktično svi ostali poznati matematički koncepti (npr dokazati, definisati, itd) zavisi dosta bitno na sistemu kojima su definisane "

Neformalna upotreba u dokazima

Dokazi u teoriji izračunljivosti često pozivaju na Čerč-Tjuringovu tezu na neformalan način da se uspostavi izračunljiva funkcija izbegavajući (često veoma dugo) detalje koji će biti uključeni u rigorozan, formalni dokaz. Da se utvrdi da je funkcija izračunljiva Tjuringovom mašinom, obično se smatra dovoljnim da se dobije neformalan engleski opis kako se funkcija može efikasno izračunati, a zatim zaključiti "Na osnovu Čerč-Tjuringove teze" da je funkcija Tjuring izračunljiva (ekvivalentno parcijalna rekurzivna).

Dirk van Dalen (u Gabaiju 2001:284) daje sledeći primer zarad ilustracije ove neformalne upotrebe Čerč-Tjuringove teze:

PRIMER: Svaki beskonačni RE skup sadrži beskonačan rekurzivni skup.

Dokaz: Neka je beskonačno Re. Navodimo elemente A efikasno, n₀, n₁, n₂, n₃, ...

Iz ovog spiska možemo izdvojiti veću podlistu: stavi m₀=n₀, posle konačno mnogo koraka možemo naći n_k takvo da n_k > m₀, stavi m₁=n_k. Ponavljamo ovu proceduru da nađemo m₂ > m₁, itd ovo daje efikasan listing na podskup B={m₀,m₁,m₂,...} od A, sa imovinom m_i < m_i+1.

Tvrdnja. B je odlučiv.Jer, da bi testirali  k u B moramo proveriti da li jek=m_i za neko i. Kako se redosled m_i's  povećava moramo proizvoditi najviše k+1 elemenata liste i porediti ih sa k. Ako ni jedan od njih nije jednak k, onda k nije u B. Dok je ovaj test efektivan, B je odlučiv i, na osnovu Čerčove teze, rekurzivan.

(Naglasak dodat). Da bi napravio gornji primer potpuno rigoroznim, jedan bi morao da pažljivo izgradi Tjuringove Mašine, ili λ-funkciju, ili pažljivo pozvati rekurzije aksiome, ili u najboljem slučaju, mudro pozivati različite teoreme teorije izračunljivosti. Ali pošto teoretičari izračunljivosti smatraju da Tjuringova izračunljivost pravilno snima ono što se može efikasno izračunati, i zato efikasna procedura je napisana na engleskom jeziku za odlučivanje u skupu V,  teoretičar izračunljivosti prihvata to kao dokaz da je skup zaista rekurzivan.

Kao pravilo, Čerč-Tjuringova teza da treba primeniti samo da se pojednostave dokazi u slučajevima u kojima bi pisac bio u stanju da, i očekuje da će čitaoci takođe da budu u stanju da, lako (ali ne nužno bez dosade) proizvodeći rigorozne dokaze ako neko od njih zahteva.

Varijacije

Uspeh Čerč-Tjuringove teze zatražio je da se varijacije teze predlože. Na primer, fizička Čerč-Tjuringova teza (FČTT) navodi:

"Sve fizički izračunljive funkcije su Tjuring-izračunljive"

Čerč-Tjuringova teza ništa ne govori o efikasnosti kojom jedan model obračuna može simulirati drugi. Dokazano je, na primer, da samo (sa više traka) univerzalna Tjuringova mašina trpi faktor logaritamskog usporavanja za simuliranje bilo koje Tjuringove Mašine. Takav rezultat je pokazao uopšte za proizvoljan, ali i razuman model izračunljivosti. Varijacija na Čerč-Tjuringovoj tezi da se bavi ovim pitanjem je Teza izvodljivosti ili (Klasična) Složeno-teorijski Čerč-Tjuringova teza (STČT), koja nije posledica Čerča ili Tjuringa, već je realizovana postepeno u razvoju teorije kompleksnosti. U njoj se navodi:

"A probabilistička Tjuringova mašina može efikasno simulirati bilo koji realan model izračunavanja."

Reč "efikasno" ovde znači do polinomskog smanjenja vremena. Ova teza je prvobitno nazvana Izračunljiva Složeno-teorijski Čerč-Tjuringova teza od Etana Bernštajna i Umeša Vaziranija (1997). Kompleksno-teorijska Čerč-Tjuringova teza, onda, pretpostavlja da će svi razumni „modeli izračunljivosti dati iste klase problema koji može da se izračuna na polinomijalnom vremenu. Pod pretpostavkom da probabilistički polinomijalno vreme (BPP) jednak determinističkom polinomijalnom vremenu (p), reč 'verovatnoće' je opciono u složeno-teorijski Čerč-Tjuringovoj tezi. Slična teza, nazvana Teza Invarijantnosti, predstavio je Ces F. Slot i Peter van Emde Boas. Ona kaže: "Razumne" mašine se mogu simulirati međusobno unutar polinomijalno ograničenom vazdušnom u vremenu i konstantnimm gornjim faktorom  u prostoru. Teza se prvobitno pojavio u novinama na STOCu'84, koji su bile prve novine da pokažu da je polinomijalno vreme gornjeg i konstantan-prostor gornjeg mogu biti istovremeno postignuta za simulaciju RAM na Tjuringovoj mašini.

Ako je BKP prikazan da bude strog nadskup BPP, to bi poništilo Složeno-teorijsku Čerč-Tjuringovu tezu. Drugim rečima, ne bi bilo efikasnih kvantnih algoritma koji obavljaju poslove koji nemaju efikasni probabilistički algoritmi. To ne bi, međutim, moglo da poništi prvobitnu Čerč-Tjuringovu tezu, jer kvantni računar može uvek da se simulira Tjuringovom mašinom, ali bi poništilo klasičnu Složeno-teorijsku Čerč-Tjuringovu tezu za efikasnost razloga. Shodno tome, Kvantno Složeno-teorijska Čerč-Tjuringova teza glasi:

"Kvantna Tjuringova mašina može efikasno simulirati bilo koji realan model izračunljivosti."

Judžin Eberbah i Peter Vegner tvrde da se Čerč-Tjuringova teza ponekad tumači previše široko, navodeći "širu tvrdnju da algoritmi upravo zauzmu ono što se može izračunati je nevažeće". Oni tvrde da oblici izračunavanja nisu zarobljeni od strane teze su relevantni danas, termini koji nazivaju super Tjuring izračunljiv.

Filozofske implikacije

Filozofi su tumačili Čerč-Tjuringovu tezu da imaju implikacije za filozofiju duha; Međutim, mnogi od filozofskih tumačenja teze uključuju osnovne nesporazume na izjave teza. B Džek Koplend kaže da je otvoreno empirijsko pitanje da li postoje stvarni deterministički fizički procesi koji, na duže staze, zaobilaze simulaciju Tjuringovom mašinom; Osim toga, on tvrdi da je otvoreno empirijsko pitanje da li su neki takvi procesi uključeni u rad ljudskog mozga. Postoje neka važna otvorena pitanja koja pokrivaju odnos između Čerč-Tjuringove teze i fizike, kao i mogućnost hiperizračunljivosti. Kada se primeni na fizici, teza ima nekoliko mogućih značenja:

1. Univerzum je ekvivalentan Tjuringovom mašinom; dakle, izračunljivost ne-rekurzivne funkcije je fizički nemoguće. Ovo je naziva Jaka Čerč-Tjuringova teza i predstavlja temelj digitalne fizike.
2. Univerzum nije ekvivalentan Tjuringovom mašinom (tj zakoni fizike nisu Tjuring-izračunljivi), ali neizračunljivi fizički događaji nisu "harnesejbl" za izgradnju hiperračunara. Na primer, univerzum u kojem fizika uključuje realne brojeve, za razliku od izračunljivosti realnih brojeva, možda spadaju u ovu kategoriju. Pretpostavka da neizračunljivi fizički događaji nisu "harnesejbl" su izazvali, međutim, predložene računarske procese koji koriste kvantnu slučajnost zajedno sa računarskim mašinama da sakriju računarske korake univerzalne Tjuringove mašine sa Tjuring-neizračunljivim zapaljivim obrascima.
3. Univerzum je hiperračunar, a moguće je izgraditi fizičke uređaje da iskoriste ovu osobinu i izračunaju ne-rekurzivne funkcije. Na primer, to je otvoreno pitanje da li su svi Kvantnomehanički događaji Tjuring-izračunljivi, iako je poznato da rigorozni modeli kao što su kvantna Tjuring mašina su ekvivalentni determinističkim Tjuringovim mašinama. (Oni nisu nužno efikasno ekvivalentni; vidi gore.) Džon Lukas i Rodžer Penrouz su sugerisali da ljudski um može biti rezultat neke vrste kvantno-mehanički pojačane, "ne-algoritmičeske" izračunljivosti, iako nema naučnih dokaza za ovaj predlog.

Postoje mnoge druge tehničke mogućnosti koje spadaju izvan ili između ove tri kategorije, ali oni služe da ilustruju opseg pojma.

Neizračunljive funkcije

Jedan formalno može definisati funkcije koje nisu izračunljive. Dobro poznati primer takve funkcije je zauzetog dabra. Ova funkcija uzima ulaz n i vraća najveći broj simbola koje Tjuringova mašina sa n stanja može da štampa pre zaustavljanja, kada se radi bez ulaza. Pronalaženje gornje granice na prometnoj funkciji dabrova je ekvivalentna rešavanju halting problema, problem poznat biti nerešiv Tjuringovim mašinama. Pošto zauzet dabar ne može da se izračuna Tjuringovim mašinama, Čerč-Tjuringova teza kaže da ova funkcija ne mogu biti efikasno izračunljiva bilo kojom metodom.

Nekoliko računarskih modela omogućavaju izračunavanje (Čerč-Tjuring) neizračunljivih funkcija. Oni su poznati kao hiperračunari. Marko Burgin tvrdi da super rekurzivni algoritmi, kao što su induktivne Tjuringove mašine opovrgnu Čerč-Tjuringovu tezu. Njegov argument počiva na definiciji algoritma šire od obične, tako da neizračunljive funkcije dobijene iz nekih induktivnih Tjuring mašina se zovu izračunljive. Ovo tumačenje Čerč-Tjuringove teze razlikuje se od tumačenja obično prihvaćenih u teoriji izračunljivosti, gore navedeno. Argument da su super rekurzivni algoritmi zaista algorimi u smislu Čerč-Tjuringove teze nije našao široko prihvatanje u Izračunljivoj istraživačkoj zajednici.

Dr Selim G Akl sa Univerziteta Kvins (Škola računanja) osporava da je Čerč-Tjuringova teza dokazivo netačno zasnovana na nizu funkcija koje su izračunljive ali generalno smatra da budu neizračunljive.

Vidi još

• Apstraktna mašina
• Čerčova teza u konstruktivnoj matematici
• Logika izračunljivosti
• Teorija izračunljivosti
• Odlučivost
• Istorija Čerč-Tjuringove teze
• Hiperračunar
• Model izračunljivosti
• Super rekurzivni algoritam
• Čerč-Tjuring-Nemački princip, koji navodi da svaki fizički proces može biti simuliran univerzalnom računarskom mašinom
• Stohastika
• Monte Carlo method

Literatura

• Barwise, Jon, H. J. Keisler, and K. Kunen, Editors, The Kleene Symposium, 426 pages, North-Holland Publishing Company, Amsterdam. Kleene, Stephen Cole (1980). The Kleene Symposium: Proceedings of the Symposium Held June 18-24, 1978 at Madison, Wisconsin, U.S.A. North-Holland Publishing Company. ISBN 978-0-444-85345-5. 
• Ben-Amram, Amir M. (2005). „The Church-Turing thesis and its look-alikes”. ACM Sigact News. 36 (3): 113—116. S2CID 13566703. doi:10.1145/1086649.1086651. 
• Bernstein, Ethan; Vazirani, Umesh (1997). „Quantum Complexity Theory”. SIAM Journal on Computing. 26 (5): 1411—1473. doi:10.1137/S0097539796300921. .
• „Algorithms: A Quest for Absolute Definitions” (PDF). oktobar 2003: 195—225. CS1 održavanje: Format datuma (veza)
• Burgin, Mark (2005). Super-recursive algorithms: Monographs in computer science. Springer. ISBN 978-0-387-95569-8. 
• Church, Alonzo (1932). „A Set of Postulates for the Foundation of Logic”. Annals of Mathematics. 33 (2): 346—366. JSTOR 1968337. doi:10.2307/1968337. 
• Church, Alonzo (1936). „An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics. 58 (58): 345—363. JSTOR 2371045. doi:10.2307/2371045. 
• Church, Alonzo (1936). „A Note on the Entscheidungsproblem”. The Journal of Symbolic Logic. 1 (1): 40—41. JSTOR 2269326. S2CID 42323521. doi:10.2307/2269326. 
• Church, Alonzo (1937). „Reviewed work: On Computable Numbers, with an Application to the Entscheidungsproblem, A. M. Turing”. The Journal of Symbolic Logic. 2 (1): 42—43. JSTOR 2268810. S2CID 73712. doi:10.2307/2268810. 
• Church, Alonzo (1941). The Calculi of Lambda-Conversion. Princeton: Princeton University Press.
• Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature". In S. B. Cooper & S. S. Goncharov. Computability and Models: Perspectives East and West. Kluwer Academic/Plenum Publishers. str. 137–160.
• Davis, Martin, ed. (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press. Includes original papers by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section.
• Eberbach, E.; Wegner, P. (October 2003). "Beyond Turing Machines". Bulletin of the European Association for Theoretical Computer Science (81): 279–304.
• Gabbay, D.M. (2001). Handbook of Philosophical Logic 1 (2nd ed.).
• Gandy, Robin (1980). "Church's Thesis and the Principles for Mechanisms". In H.J. Barwise, H.J. Keisler, and K. Kunen. The Kleene Symposium. North-Holland Publishing Company. str. 123–148.
• Gandy, Robin; Rolf Herken, ed. The universal Turing Machine: A Half-Century Survey. New York: Wien Springer–Verlag. ISBN 978-3-211-82637-9. CS1 održavanje: Tekst viška: spisak autora (veza)
• Gödel, Kurt (1965) [1934]. "On Undecidable Propositions of Formal Mathematical Systems". In Davis, M. The Undecidable. Kleene and Rosser (lecture note-takers); Institute for Advanced Study (lecture sponsor). New York: Raven Press.
• Gödel, Kurt (1936). "On The Length of Proofs". Ergenbnisse eines mathematishen Kolloquiums (in German) (Heft) (7): 23–24. Cited by Kleene (1952) as "Über die Lāange von Beweisen", in Ergebnisse eines math. Koll, etc.
• Gurevich, Yuri (June 1988). "On Kolmogorov Machines and Related Issues". Bulletin of European Association for Theoretical Computer Science (35): 71–82.
• „Microsoft Research – Emerging Technology, Computer, and Software Research” (PDF). 
• Gurevich, Yuri (2000). „Sequential abstract-state machines capture sequential algorithms”. ACM Transactions on Computational Logic. 1 (1): 77—111. S2CID 2031696. doi:10.1145/343369.343384. 
• Herbrand, Jacques (1932). "Sur la non-contradiction de l'arithmétique". Journal fur die reine und angewandte Mathematik (166): 1–8.
• Hofstadter, Douglas R.. "Chapter XVII: Church, Turing, Tarski, and Others". Gödel, Escher, Bach: an Eternal Golden Braid.
• Kleene, S. C. (1935). „A Theory of Positive Integers in Formal Logic. Part I”. American Journal of Mathematics. 57 (1): 153—173. JSTOR 2372027. doi:10.2307/2372027. 
• Kleene, S. C. (1936). „λ-definability and recursiveness”. Duke Mathematical Journal. 2 (2). doi:10.1215/s0012-7094-36-00227-2. 
• Kleene, S. C. (1943). „Recursive Predicates and Quantifiers”. Transactions of the American Mathematical Society. 54 (1): 41—73. JSTOR 1990131. doi:10.2307/1990131. * Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. OCLC 523942.
• Knuth, Donald (1973). The Art of Computer Programming. 1/Fundamental Algorithms (2nd ed.). Addison–Wesley.
• Kugel, Peter (November 2005). "Communications of the ACM". It's time to think outside the computational box 48 (11).
• Lewis, H.R.; Papadimitriou, C.H. (1998). Elements of the Theory of Computation. Upper Saddle River, NJ, USA: Prentice-Hall.
• Manna, Zohar (2003) [1974]. Mathematical Theory of Computation. Dover. ISBN 978-0-486-43238-0. 
• Markov, A.A. (1960) [1954]. "The Theory of Algorithms". American Mathematical Society Translations American Mathematical Society Translations. 2 (15): 1—14. 1960.  .
• Olszewski, Adam (2006). Church's Thesis After 70 Years.
• Pour-El, M.B.; Richards, J.I. (1989). Computability in Analysis and Physics. Springer Verlag.
• Rosser, Barkley (1939). „An Informal Exposition of Proofs of Gödel's Theorems and Church's Theorem”. The Journal of Symbolic Logic. 4 (2): 53—60. JSTOR 2269059. S2CID 39499392. doi:10.2307/2269059. 
• Sieg, Wilfried; Sommer, Richard; Talcott, Carolyn, ur. (16. 8. 2002). Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman: Lecture Notes in Logic 15. Taylor & Francis. ISBN 978-1-56881-169-7. CS1 održavanje: Format datuma (veza)
• Soare, Robert (1996). "Computability and Recursion". Bulletin of Symbolic Logic (2): 284–321.
• Syropoulos, Apostolos (2008). Hypercomputation: Computing Beyond the Church-Turing Barrier. Springer. ISBN 978-0-387-30886-9. 
• Turing, A. M. (1937). „On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society: 230—265. S2CID 73712. doi:10.1112/plms/s2-42.1.230. 
• Turing, A. M. (1938). „On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction”. Proceedings of the London Mathematical Society: 544—546. doi:10.1112/plms/s2-43.6.544.  (See also: Davis 1965:115ff)

Spoljašnje veze

• The Church–Turing Thesis entry by B. Jack Copeland in the Stanford Encyclopedia of Philosophy.
• Computation in Physical Systems —a comprehensive philosophical treatment of relevant issues
• Transcendental idealism and Post’s variant of the Church-Turing thesis —EGTheory blog