Sari la conținut

Teza Church-Turing

De la Wikipedia, enciclopedia liberă

În teoria calculabilității, teza Church-Turing (cunoscută și sub numele de teza calculabilității,[1] teza Turing-Church,[2] 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[3] și Turing[4] 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

[modificare | modificare sursă]

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»”.[5][6]

Î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.[7]

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

[modificare | modificare sursă]

Una dintre problemele importante pentru logicienii din anii 1930 era Entscheidungsproblem a lui David Hilbert și Wilhelm Ackermann, [8] 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.[9] Dar încă de la început încercările lui Alonzo Church au început cu o dezbatere care continuă până în ziua de astăzi.[10] 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

[modificare | modificare sursă]

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

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ă.[11] Pe de altă parte, articolul Emil Post⁠(d) 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”.[12] Această idee a fost „aspru” criticată de Church.[13]

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.[14]

În scurt timp, a apărut lucrarea lui Turing din 1936–37 „Despre numere calculabile, cu aplicație la Entscheidungsproblem” [11] Î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)”.[15]

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

Aceasta i-a lăsat lui Kleene formularea deschisă a unei „teze”. În lucrarea sa din 1943 Recursive Predicates and Quantifiers, Kleene și-a avansat „TEZA I”:

(24) face referire la definițiile formale din teoria numerelor ordinale, Fund. Math. vol 28 (1936) pp. 11–21 (vezi ref. # 2, Davis 1965 ).

În anii 1939-1952, Stephen Kleene a continuat să numească în mod deschis, după ce a trecut de la prezentarea lucrării sale în terminologia matematică a calculului lambda la propria sa teorie a funcțiilor recursive parțiale sau recursivitatea Gödel-Kleene, atât teza lui Church, cât și teza lui Turing. În cele din urmă, el a fixat termenul „teza Church-Turing” într-o secțiune din manualul său universitar de logică, manual în care ajuta la oferirea de clarificări conceptelor, cerute într-o critică a lui William Boone pe lucrarea lui Alan Turing „The Word Problem in Semi-Groups with Cancellation”, și a apărat și exprimat cele două „teze” și apoi le-a „identificat” (le-a demonstrat echivalența) prin utilizarea teoremei sale XXX:

Teza ca definiție

[modificare | modificare sursă]

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”.[17] Argumentația acestei idei este făcută în mod explicit de Robert I. Soare⁠(d),[18] 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.

Note

[modificare | modificare sursă]
  1. ^ Robert Soare⁠(d), "Turing Oracle Machines, Online Computing, and Three Displacements in Computability Theory"
  2. ^ Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. 1 iunie 2012. http://videolectures.net/turing100_rabin_turing_church_goedel/. 
  3. ^ Church 1936.
  4. ^ Turing 1937a.
  5. ^ Merriam Webster's New Collegiate Dictionary (ed. 9th). 
  6. ^ See also Merriam-Webster's Online Dictionary (ed. 11th). Accesat în ,  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").
  7. ^ Turing, A.M. (). Systems of Logic Based on Ordinals (PDF) (PhD). Princeton University. p. 8. Arhivat din original (PDF) la . Accesat în . 
  8. ^ David Hilbert and Wilhelm Ackermann: Grundzüge der theoretischen Logik, Berlin, Germany, Springer, 1st ed. 1928. (6th ed. 1972, ISBN: 3-540-05843-5) English Translation: David Hilbert and Wilhelm Ackermann: Principles of Mathematical Logic, AMS Chelsea Publishing, Providence, Rhode Island, USA, 1950
  9. ^ 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.
  10. ^ 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
  11. ^ a b Turing 1937. .
  12. ^ Post 1936 in Davis 1952:291.
  13. ^ Sieg 1997:171 and 176–177.
  14. ^ Sieg 1997:160.
  15. ^ Church 1937. .
  16. ^ Turing 1939 in Davis:160.
  17. ^ Gödel, Kurt () [193?]. „Undecidable Diophantine Propositions”. În Feferman, Solomon. Collected Works. 3. New York: Oxford University Press. p. 168. ISBN 978-0-19-507255-6. OCLC 928791907. 
  18. ^ Soare, Robert I. (septembrie 1996). „Computability and Recursion”. Bulletin of Symbolic Logic. 2 (3): 284–321. doi:10.2307/420992. JSTOR 420992. 
Adus de la https://ro.wikipedia.org/w/index.php?title=Teza_Church-Turing&oldid=14737183