Teza Church-Turing

În teoria calculabilității, teza Church-Turing (cunoscută și sub numele de teza calculabilității, teza Turing-Church, conjectura Church-Turing, teza lui Church, conjectura lui Church sau teza lui Turing) este o ipoteză despre natura funcțiilor calculabile^⁠(d). Ea afirmă că o funcție definită pe mulțimea numerelor naturale poate fi calculată printr-o metodă efectivă^⁠(d) 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 calculabilitate^⁠(d):

• În 1933, Kurt Gödel, împreună cu Jacques Herbrand^⁠(d), au creat o definiție formală a unei clase numite funcții general recursive^⁠(d). 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, funcția succesor^⁠(d) și care este închisă în raport cu compoziția funcțiilor^⁠(d), recursivitatea și minimizarea^⁠(d).
• În 1936, Alonzo Church a creat o metodă de definire a funcțiilor numită calculul λ^⁠(d). În cadrul calculului λ, el a definit o codificare a numerelor naturale denumită codificarea Church^⁠(d). 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ă^⁠(d) 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 fizica numerică^⁠(d). 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»”.

Î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, Sisteme de logică bazate pe ordinali^⁠(d), 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, 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. Dar încă de la început încercările lui Alonzo Church au început cu o dezbatere care continuă până în ziua de astăzi. 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 funcții λ-definibile^⁠(d) ș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ă:

Singura idee a lui [Gödel] de atunci era că s-ar putea să fie posibil, în termeni de calculabilitate efectivă ca noțiune nedefinită, să se enunțe un set de axiome care să întrupeze proprietățile general acceptate ale acestei noțiuni, și să se construiască ceva pe acea bază.

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 J. Barkley Rosser^⁠(d), 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 formulă bine formată^⁠(d) 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 [1934], 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:

„De fapt, lucrările deja realizate de Church și de alții duc această identificare considerabil dincolo de faza unei ipoteze de lucru. Dar pentru a masca această identificare sub o definiție ... ne ascunde nevoia verificării ei continue.”

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”. Această idee a fost „aspru” criticată de Church.

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.

Î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ă. 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:

„Toate cele trei definiții sunt echivalente, așa că nu contează care se folosește.”

În 1943, Kleene a propus „Teza I”:

„Acest fapt euristic [că funcțiile general recursive sunt efectiv calculabile] ... l-a condus pe Church să enunțe următoarea teză. Aceeași teză este implicită în descrierea făcută de Turing mașinilor de calcul.

„Teza I. Orice funcție efectiv calculabilă (predicat efectiv decidabil) este general recursiv [sublinierile îi aparțin lui Kleene]”

Întrucât ne lipsește o definiție matematică precisă a termenului «efectiv calculabil» (efectiv decidabil), putem lua această teză ... drept definiția lui ...”

„...teza are caracterul de ipoteză—o idee subliniată de Post și de Church. Dacă considerăm teza și reciproca ei drept definiție, atunci ipoteza este una despre aplicarea teoreiei matematice dezvoltate din definiție. Pentru acceptarea ipotezei, există, după cum am sugerat, fundamente convingătoare.”

În Introduction to Metamathematics, Stephen Kleene numește aceasta în mod formal „teza lui Church” „teza lui Turing”, folosind teoria realizabilității recursive enunțată de el, după ce a renunțat la a-și prezenta lucrarea în terminologia definibilității lambda Church–Kleene în favoarea recursivității Gödel–Kleene (funcții parțial recursive). În această tranziție, Kleene a modificat funcțiile general recursive ale lui Gödel pentru a permite demonstrarea nerezolvabilității unor probleme în intuiționismul lui E. J. Brouwer. În manualul său universitar despre logică, este introdusă „teza lui Church” și se demonstreaza că rezultatele matematice de bază sunt nerealizabile. Apoi, Kleene prezintă „teza lui Turing”, în care se demonstrează că rezultatele sunt necalculabile, folosind calculul simplificat al unei mașini Turing pe baza lucrărilor lui Emil Post. Se demonstrează că cele două teze sunt echivalente prin utilizarea „Teoremei XXX”.

„Teza I. Orice funcție efectiv calculabilă (predicat efectiv decidabil) este general recursivă.”

„Teorema XXX: Următoarele clase de funcții parțiale sunt coextensive, adică au aceiași membri: (a) funcțiile parțial recursive, (b) funcțiile calculabile ...”

„Teza lui Turing: Teza lui Turing conform căreia orice funcție care ar fi în mod natural considerată calculabilă sub definiția lui, adică de către una din mașinile lui, este echivalentă cu teza lui Church conform Teoremei XXX.”

În fine, Kleene a utilizat pentru prima oară termenul de „teza Church-Turing” într-o secțiune în care încearcă să dea clarificări conceptelor din lucrarea lui Alan Turing „The Word Problem in Semi-Groups with Cancellation”, la cererea unei critici din partea lui William Boone.

Teza ca definiție

Teza poate fi privită și doar ca o definiție matematică obișnuită. Comentariile lui Gödel cu privire la acest subiect sugerează acest punct de vedere, de exemplu „definiția corectă a calculabilității mecanice a fost stabilită fără nici o îndoială de către Turing”. Argumentația acestei idei este făcută în mod explicit de Robert I. Soare^⁠(d), care susține, de asemenea, că definiția calculabilității a lui Turing nu este mai puțin probabil să fie corectă decât definiția epsilon-delta a unui funcții continue.

Bibliografie

• Barwise, Jon; Keisler, H.J.; Kunen, Kenneth, ed. (1980). The Kleene Symposium. Amsterdam: North-Holland Publishing Company. ISBN 978-0-444-85345-5. 
• Ben-Amram, A. M. (2005). „The Church-Turing Thesis and its Look-Alikes”. SIGACT News. 36 (3): 113–116. CiteSeerX 10.1.1.74.7308 . doi:10.1145/1086649.1086651. Arhivat din original (PS) la 6 iulie 2017. Accesat în 24 octombrie 2017. 
• Bernstein, E.; Vazirani, U. (1997). „Quantum complexity theory”. SIAM Journal on Computing. 26 (5): 1411–1473. CiteSeerX 10.1.1.655.1186 . doi:10.1137/S0097539796300921. 
• Blass, Andreas; Gurevich, Yuri (octombrie 2003). „Algorithms: A Quest for Absolute Definitions” (PDF). Bulletin of European Association for Theoretical Computer Science (81). Arhivat din original (PDF) la 27 iulie 2004. 
• 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. doi:10.2307/1968337. JSTOR 1968337. 
• Church, Alonzo (1936). „An Unsolvable Problem of Elementary Number Theory” (PDF). American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045. Arhivat din original (PDF) la 27 februarie 2020. 
• Church, Alonzo (1936). „A Note on the Entscheidungsproblem”. Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326. 
• Church, Alonzo (martie 1937). „Review: A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem”. Journal of Symbolic Logic. 2 (1): 42–43. doi:10.2307/2268810. JSTOR 2268810. 
• Church, Alonzo (1941). The Calculi of Lambda-Conversion. Princeton: Princeton University Press. 
• Cooper, S. B.; Odifreddi, P. (2003). „Incomputability in Nature”. În S. B. Cooper; S. S. Goncharov. Computability and Models: Perspectives East and West. Kluwer Academic/Plenum Publishers. pp. 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.
• Dawson, John W. Jr. (1997). Logical Dilemmas: The Life and Work of Kurt Gödel. Wellesley, Massachusetts, US: A. K. Peters. 
• Eberbach, E.; Wegner, P. (octombrie 2003). „Beyond Turing Machines” (PDF). Bulletin of the European Association for Theoretical Computer Science (81): 279–304. CiteSeerX 10.1.1.61.9759 . Arhivat din original (PDF) la 15 martie 2016. 
• Gabbay, D. M. (2001). Handbook of Philosophical Logic. 1 (ed. 2nd). 
• Gandy, Robin (1980). „Church's Thesis and the Principles for Mechanisms”. În H. J. Barwise; H. J. Keisler; K. Kunen. The Kleene Symposium. North-Holland Publishing Company. pp. 123–148. 
• Gandy, Robin (1994). Herken, Rolf, ed. The universal Turing Machine: A Half-Century Survey. New York: Wien Springer–Verlag. pp. 51ff. ISBN 978-3-211-82637-9. 
• Gödel, Kurt (1965). „On Undecidable Propositions of Formal Mathematical Systems”. În Davis, Martin. The Undecidable. Kleene and Rosser (lecture note-takers); Institute for Advanced Study (lecture sponsor). New York: Raven Press. 
• Gödel, Kurt (1936). „Über die Lāange von Beweisen” [On The Length of Proofs]. Ergenbnisse Eines Mathematishen Kolloquiums (în germană). Heft (7): 23–24.  Cited by Kleene (1952).
• Gurevich, Yuri (iunie 1988). „On Kolmogorov Machines and Related Issues”. Bulletin of European Association for Theoretical Computer Science (35): 71–82. 
• Gurevich, Yuri (iulie 2000). „Sequential Abstract State Machines Capture Sequential Algorithms” (PDF). ACM Transactions on Computational Logic. 1 (1): 77–111. CiteSeerX 10.1.1.146.3017 . doi:10.1145/343369.343384. Arhivat din original (PDF) la 16 octombrie 2003. 
• Herbrand, Jacques (1932). „Sur la non-contradiction de l'arithmétique”. Journal für die Reine und Angewandte Mathematik (în franceză). 166: 1–8. doi:10.1515/crll.1932.166.1. 
• Hofstadter, Douglas R. (5 februarie 1999). „Chapter XVII: Church, Turing, Tarski, and Others”. Gödel, Escher, Bach: an Eternal Golden Braid (ed. Twentieth-anniversary). Basic Books. pp. 559–585. ISBN 0-465-02656-7. 
• Kleene, Stephen Cole (ianuarie 1935). „A Theory of Positive Integers in Formal Logic”. American Journal of Mathematics. 57 (1): 153–173 & 219–244. doi:10.2307/2372027. JSTOR 2372027. 
• Kleene, Stephen Cole (1936). „Lambda-Definability and Recursiveness”. Duke Mathematical Journal. 2 (2): 340–353. doi:10.1215/s0012-7094-36-00227-2. 
• Kleene, Stephen Cole (1943). „Recursive Predicates and Quantifiers”. Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.2307/1990131 . JSTOR 1990131.  Reprinted in The Undecidable, p. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in Format:Harvcolnb) and name it "Church's Thesis" (Kleene 1952) (i.e., the Church thesis).
• Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. OCLC 523942. 
• Knuth, Donald (1973). The Art of Computer Programming. 1/Fundamental Algorithms (ed. 2nd). Addison–Wesley. 
• Kugel, Peter (noiembrie 2005). „It's time to think outside the computational box”. Communications of the ACM. 48 (11): 32–37. CiteSeerX 10.1.1.137.6939 . doi:10.1145/1096000.1096001. 
• Lewis, H.R.; Papadimitriou, C.H. (1998). Elements of the Theory of Computation. Upper Saddle River, New Jersey, US: Prentice-Hall. 
• Manna, Zohar (2003). Mathematical Theory of Computation. Dover. ISBN 978-0-486-43238-0. 
• Markov, A. A. (1960). „The Theory of Algorithms”. American Mathematical Society Translations. 2 (15): 1–14. 
• Olszewski, Adam; Woleński, Jan; Janusz, Robert, ed. (2006). Church's Thesis After 70 Years. Frankfurt: Ontos. ISBN 978-3-938793-09-1. OCLC 909679288. 
• Pour-El, M. B.; Richards, J.I. (1989). Computability in Analysis and Physics. Springer Verlag. 
• Rosser, J. B. (1939). „An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem”. The Journal of Symbolic Logic. 4 (2): 53–60. doi:10.2307/2269059. JSTOR 2269059. 
• Sieg, Wilfried; Sommer, Richard; Talcott, Carolyn, ed. (2002). Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman. Lecture Notes in Logic. 15. A. K. Peters, Ltd. ISBN 978-1-56881-169-7. 
• 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” (PDF), Proceedings of the London Mathematical Society, 2, 42, pp. 230–265, Bibcode:1937PLMS...42..230T, doi:10.1112/plms/s2-42.1.230  and Turing, A. M. (1938). „On Computable Numbers, with an Application to the Entscheidungsproblem: A correction”. Proceedings of the London Mathematical Society. 2. 43 (publicat la 1937). pp. 544–546. doi:10.1112/plms/s2-43.6.544.  (See also: Format:Harvcolnb)
• Turing, Alan Mathison (1937). „Computability and λ-Definability” (PDF). Journal of Symbolic Logic. 2 (4): 153–163. doi:10.2307/2268280. JSTOR 2268280. Arhivat din original (PDF) la 9 august 2020.