În teoria calculabilității, teza Church-Turing (cunoscută și sub numele de teza calculabilității,, "Turing Oracle Machines, Online Computing, and Three Displacements in Computability Theory" teza Turing-Church, conjectura Church-Turing, teza lui Church, conjectura lui Church sau teza lui Turing) este o ipoteză despre natura funcțiilor calculabile. Ea afirmă că o funcție definită pe mulțimea numerelor naturale poate fi calculată printr-o dacă și numai dacă este calculabilă de o mașină Turing. Teza își trage numele de la matematicianul american Alonzo Church și de la matematicianul britanic Alan Turing. Înainte de definirea precisă a funcțiilor calculabile, matematicienii foloseau adesea termenul informal de efectiv calculabil pentru a descrie funcții care pot fi calculate prin metode cu hârtia și creionul. În anii 1930, s-au făcut mai multe încercări independente de a formaliza noțiunea de :
În 1933, Kurt Gödel, împreună cu , au creat o definiție formală a unei clase numite . Clasa funcțiilor general recursive este cea mai restrânsă clasă de funcții (posibil cu mai multe argumente) care cuprinde toate funcțiile constante, proiecțiile, și care este închisă în raport cu , recursivitatea și . În 1936, Alonzo Church a creat o metodă de definire a funcțiilor numită . În cadrul calculului λ, el a definit o codificare a numerelor naturale denumită . O funcție definită pe mulțimea numerelor naturale se numește λ-calculabilă dacă funcția corespunzătoare definită pe mulțimea numerelor Church poate fi reprezentată printr-un termen al calculului λ. Tot în 1936, înainte de a afla de lucrarea lui Church, Alan Turing a creat un model teoretic pentru mașinile de calcul, denumit astăzi mașina Turing, care putea efectua calcule pe baza unor date de intrare manipulând simboluri pe o bandă. Dată fiind o codificare adecvată a numerelor naturale ca secvențe de simboluri, o funcție definită pe mulțimea numerelor naturale se numește Turing calculabilă dacă o mașină Turing calculează funcția corespunzătoare pe numerele naturale codificate.
Church, Kleene, și Turing au demonstrat că aceste trei clase definite formal de funcții calculabile coincid: o funcție este λ-calculabilă dacă și numai dacă este calculabilă Turing și dacă și numai dacă este general recursivă. Acest lucru i-a determinat pe matematicieni și informaticieni să creadă că conceptul de calculabilitate este caracterizat cu exactitate de aceste trei procese echivalente. Alte încercări formale de a caracteriza calculabilitatea au consolidat ulterior această credință.
Pe de altă parte, teza Church-Turing afirmă că cele trei clase definite formal de funcții calculabile de mai sus coincid cu noțiunea informală de funcție efectiv calculabilă. Deoarece, fiind o noțiune informală, conceptul de calculabilitate efectivă nu are o definiție formală, deși are o acceptare aproape universală, teza nu poate fi demonstrată formal.
Încă de la începuturile sale, au apărut variații ale tezei originare, inclusiv afirmații despre ceea ce poate fi realizat fizic de un computer din universul nostru (teza Church-Turing fizică) și ce poate fi calculat cu eficiență (teza Church-Turing în teoria complexității). Aceste variații nu se datorează nici lui Church, nici lui Turing, ci apar din lucrările ulterioare în teoria complexității și . Teza are implicații și pentru filosofia minții.
Enunțul în cuvintele lui Church și ale lui Turing J. B. Rosser (1939) tratează noțiunea de „calculabilitate efectivă” astfel: „este clar că existența CC și RC (demonstrațiile lui Church și a lui Rosser) presupune o definiție precisă a noțiunii de «efectiv». Ideea de «metodă efectivă» este folosită aici într-un sens oarecum specific de metodă al cărei fiecare pas este predeterminat precis și care va produce cu certitudine răspunsul într-un număr finit de pași". Astfel, adverbul-adjectiv «efectiv» este utilizat în sensul de «1a: care produce un efect determinat, decisiv, sau dorit», și «capabil de a produce un rezultat»”.See also which also gives these definitions for "effective" – the first ["producing a decided, decisive, or desired effect"] as the definition for sense "1a" of the word "effective", and the second ["capable of producing a result"] as part of the "Synonym Discussion of EFFECTIVE" there, (in the introductory part, where it summarizes the similarities between the meanings of the words "effective", "effectual", "efficient", and "efficacious").
În cele ce urmează, cuvintele „efectiv calculabil” vor însemna „produs prin orice mijloc intuitiv «efectiv»”, iar „efectiv calculabil” va însemna „produs de o mașină Turing sau de un dispozitiv mecanic echivalent”. „Definițiile” lui Turing date într-o notă de subsol în teza sa de doctorat din 1938, , sub îndrumarea lui Church, sunt practic aceleași:Vom utiliza expresia „funcție calculabilă” cu sensul de funcție calculabilă de către o mașină, și fie expresia „efectiv calculabil” să se refere la ideea intuitivă fără identificare particulară cu vreuna din aceste definiții.Teza poate fi formulată astfel: Orice funcție efectiv calculabilă este o funcție calculabilă. Church a mai afirmat că „nicio procedură de calcul nu va fi considerată algoritm decât dacă poate fi reprezentată ca mașină Turing”. Turing o formula astfel:S-a afirmat ... că „o funcție este efectiv calculabilă dacă valorile sale pot fi găsite printr-un proces pur mecanic.” Putem lua acest lucru la propriu, înțelegând printr-un proces pur mecanic unul care ar putea fi efectuat de o mașină. Dezvoltarea ... conduce la ... o identificare a calculabilității cu calculabilitatea efectivă. [ este nota de subsol citată mai sus. ]
Istorie Una dintre problemele importante pentru logicienii din anii 1930 era Entscheidungsproblem a lui David Hilbert și Wilhelm Ackermann, David Hilbert and Wilhelm Ackermann: Grundzüge der theoretischen Logik, Berlin, Germany, Springer, 1st ed. 1928. (6th ed. 1972, ) English Translation: David Hilbert and Wilhelm Ackermann: Principles of Mathematical Logic, AMS Chelsea Publishing, Providence, Rhode Island, USA, 1950 care pune întrebarea dacă există o procedură mecanică pentru separarea adevărurilor matematice de falsurile matematice. Această căutare necesita ca noțiunea de „algoritm” sau „calculabilitate efectivă” să fie fixate, cel puțin suficient de bine pentru a începe cercetarea.Davis's commentary before Church 1936 An Unsolvable Problem of Elementary Number Theory in Davis 1965:88. Church uses the words "effective calculability" on page 100ff. Dar încă de la început încercările lui Alonzo Church au început cu o dezbatere care continuă până în ziua de astăzi.In his review of Church's Thesis after 70 Years edited by Adam Olszewski et al. 2006, Peter Smith's criticism of a paper by Muraswski and Wolenski suggests 4 "lines" re the status of the Church–Turing Thesis: (1) empirical hypothesis (2) axiom or theorem, (3) definition, (4) explication. But Smith opines that (4) is indistinguishable from (3), cf Smith (July 11, 2007) Church's Thesis after 70 Years at http://www.logicmatters.net/resources/pdfs/CTT.pdf Noțiunea de „calculabilitate efectivă” urma a fi fie (i) o „axiomă sau mai multe” într-un sistem axiomatic, fie (ii) doar o definiție care „identifica” două sau mai multe propoziții, fie (iii) o ipoteză empirică care trebuie verificată prin observarea evenimentelor naturale, fie (iv) doar o propunere de dragul argumentării (adică o „teză”).
Circa 1930–1952 În cursul studierii problemei, Church și studentul său Stephen Kleene au introdus noțiunea de și au reușit să demonstreze că mai multe clase mari de funcții întâlnite frecvent în teoria numerelor erau λ-definibile. Dezbaterea a început când Church i-a propus lui Gödel să definească funcțiile „efectiv calculabile” ca funcții λ-definibile. Cu toate acestea, Gödel nu a fost convins și a considerat această propunere „complet nesatisfăcătoare”. În corespondența cu Church (c. 1934–35), Gödel propunea în schimb axiomatizarea noțiunii de „calculabilitate efectivă”; într-adevăr, într-o scrisoare din 1935 către Kleene, Church consemna că:
Dar Gödel nu a oferit alte îndrumări. În cele din urmă, el sugera recursivitatea sa, modificată de sugestia lui Herbrand, pe care Gödel o detaliase în prelegerile sale din 1934 din Princeton NJ (Kleene și Rosser au transcris notele). Dar el nu credea că cele două idei pot fi identificate în mod satisfăcător „decât poate euristic”.
Apoi, a fost necesar să se identifice și să se demonstreze echivalența a două noțiuni de calculabilitate efectivă. Echipat cu calculul λ și cu recursivitatea „generală”, Stephen Kleene cu ajutorul lui Church și , a produs demonstrații (1933, 1935) ce arătau că cele două calcule sunt echivalente. Ulterior, Church și-a modificat metodele pentru a include utilizarea recursivității Herbrand–Gödel și apoi a demonstrat (1936) că Entscheidungsproblem nu se poate rezolva: nu există niciun algoritm care să poată determina dacă o are o „formă normală”.
Mulți ani mai târziu, într-o scrisoare către Davis (c. 1965), Gödel spunea că „în momentul acestor conferințe , nu era deloc convins că conceptul său de recursivitate cuprinde toate recursiile posibile”. Până în 1963–64 Gödel a dezavuat recursivitatea Herbrand–Gödel și calculul λ în favoarea mașinii Turing ca definiție a „algoritmului” sau „procedurii mecanice” sau „sistemului formal”.
La sfârșitul anului 1936, lucrarea lui Alan Turing (care demonstrează, de asemenea, că Entscheidungsproblem este nerezolvabilă) a fost susținută oral, dar nu fusese tipărită.. Pe de altă parte, articolul lui Emil Post din 1936 apăruse și era certificat independent de lucrarea lui Turing. Post nu era de acord cu „identificarea” de către Church a calculabilității efective cu calculul λ și cu recursivitatea, afirmând:
El considera în schimb noțiunea de „calculabilitate efectivă” ca doar o „ipoteză de lucru” care ar putea conduce prin raționament inductiv la o „lege naturală” mai degrabă decât prin „definiții sau axiome”.Post 1936 in Davis 1952:291. Această idee a fost „aspru” criticată de Church.Sieg 1997:171 and 176–177.
Astfel, în lucrarea sa din 1936, Post refuza și sugestia lui Kurt Gödel către Church din 1934–35 că teza ar putea fi exprimată ca o axiomă sau un set de axiome.Sieg 1997:160.
În scurt timp, a apărut lucrarea lui Turing din 1936–37 „Despre numere calculabile, cu aplicație la Entscheidungsproblem” . În ea, el formula o altă noțiune a „calculabilității efective” odată cu introducerea mașinilor sale a (cunoscute acum ca modelul computațional abstract al mașinii Turing). Și într-o schiță de demonstrație adăugată ca „Anexă” la lucrarea sa din 1936–37, Turing arăta că clasele de funcții definite de calculul λ și de mașinile Turing coincideau. Church a recunoscut rapid cât de convingătoare este analiza lui Turing. În trecerea în revistă a lucrării lui Turing, el a arătat clar că noțiunea lui Turing făcea „imediat evidentă identificarea cu efectivitatea în sensul obișnuit (nedefinit în mod explicit)”..
În câțiva ani (1939) Turing avea să propună, la fel ca Church și Kleene înaintea sa, că definiția sa formală a agentului de calcul mecanic era cea corectă.Turing 1939 in Davis:160. Astfel, până în 1939, atât Church (1934), cât și Turing (1939) propuseseră individual că „sistemele lor formale” ar trebui să fie definiții ale „calculabilității efective”; niciunul dintre ei nu și-a încadrat declarațiile ca teză.
Rosser (1939) a identificat formal cele trei noțiuni-ca-definiții:
În 1943, Kleene a propus „Teza I”: în . Note de subsol omise.