close
Sari la conținut

Turing-completitudine

De la Wikipedia, enciclopedia liberă

În teoria calculabilității, un sistem de reguli de manipulare a datelor (cum ar fi un model de calcul, setul de instrucțiuni al unui calculator, un limbaj de programare sau un automat celular) se numește Turing-complet sau universal computațional dacă poate fi utilizat pentru a simula orice mașină Turing[1][2] (concepută de matematicianul și informaticianul englez Alan Turing). Aceasta înseamnă că sistemul în chestiune este capabil să recunoască sau să decodifice alte seturi de reguli de manipulare a datelor. Turing-completitudinea este utilizată ca modalitate de a exprima puterea unui astfel de set de reguli de manipulare a datelor. Practic toate limbajele de programare actuale sunt Turing-complete.[a]

Un concept înrudit este cel de echivalență Turing – Două calculatoare P și Q sunt Turing-echivalente dacă P poate simula Q și Q poate simula P.[4] Teza Church-Turing presupune că orice funcție ale cărei valori pot fi calculate de un algoritm poate fi calculată de o mașină Turing și, prin urmare, dacă orice calculator din lumea reală poate simula o mașină Turing, acesta este Turing echivalent cu o mașină Turing. O mașină Turing universală poate fi utilizată pentru a simula orice mașină Turing și, prin extensie, aspectele pur computaționale ale oricărui calculator posibil din lumea reală.[5][6]

Pentru a demonstra că ceva este Turing-complet, este suficient să se demonstreze că poate fi folosit pentru a simula un sistem Turing-complet. Niciun sistem fizic nu poate avea memorie infinită, dar dacă limitarea memoriei finite este ignorată, majoritatea limbajelor de programare sunt Turing-complete.[7][8]

Utilizare în afara matematicii

[modificare | modificare sursă]

În uzul colocvial, termenii „Turing-complet” și „Turing-echivalent” sunt folosiți pentru a însemna că orice calculator sau limbaj de calculator de uz general din lumea reală poate simula aproximativ aspectele computaționale ale oricărui alt calculator sau limbaj de calculator de uz general din lumea reală. În viața reală, aceasta se traduce prin conceptele practice de virtualizare și emulare a mașinilor de calcul.

Calculatoarele reale construite până în prezent pot fi analizate funcțional ca o mașină Turing cu o singură bandă (care folosește o „bandă” pentru memorie); astfel, matematica asociată se poate aplica prin abstractizarea suficientă a funcționării lor. Calculatoarele reale au însă resurse fizice limitate, deci sunt doar automate liniar mărginite complete. Abstractizarea unui calculator universal este, dimpotrivă, definită ca un dispozitiv cu un set de instrucțiuni Turing complet, memorie infinită și timp disponibil infinit.

Definiții formale

[modificare | modificare sursă]

În teoria calculabilității, există mai mulți termeni strâns înrudiți care sunt utilizați pentru a descrie puterea de calcul a unui sistem de calcul (cum ar fi o mașină abstractă sau un limbaj de programare):

Turing-completitudinea
Un sistem de calcul care poate calcula orice funcție Turing-calculabilă se numește Turing-completă (sau Turing-puternică). Un astfel de sistem poate fi definit și ca unul care poate simula o mașină Turing universală.
Turing-echivalența
Un sistem Turing-complet se numește Turing-echivalent dacă orice funcție pe care o poate calcula este și Turing-calculabilă; adică, calculează exact aceeași clasă de funcții ca și mașinile Turing. Un sistem Turing-echivalent poate fi definit și ca unul care poate simula și poate fi simulat de o mașină Turing universală. (Toate sistemele Turing-complete implementabile fizic cunoscute sunt Turing-echivalente, ceea ce adaugă sprijin tezei Church-Turing.)
Universalitate (computațională)
Un sistem se numește universal în raport cu o clasă de sisteme dacă poate calcula orice funcție calculabilă de către sistemele din acea clasă (sau poate simula fiecare dintre aceste sisteme). De obicei, termenul „universalitate” este implicit în referirea cu privire la o clasă de sisteme Turing-complete. Se mai folosește termenul „slab universal” uneori pentru a distinge un sistem (de exemplu, un automat celular) a cărui universalitate se obține doar prin modificarea definiției standard a mașinii Turing, astfel încât să includă fluxuri de intrare cu o infinitate de unități.

Istorie

[modificare | modificare sursă]

Turing-completitudinea este semnificativă prin faptul că orice design din lumea reală pentru un dispozitiv de calcul poate fi simulat de o mașină Turing universală. Teza Church-Turing afirmă că aceasta este o lege a matematicii – că o mașină Turing universală poate, în principiu, efectua orice calcul pe care îl poate efectua orice alt calculator programabil. Aceasta nu spune însă nimic despre efortul necesar pentru a scrie programul, despre timpul care i-ar putea lua mașinii să efectueze calculul sau despre orice abilități pe care mașina le-ar putea poseda și care nu au nicio legătură cu calculul.

Motorul analitic al lui Charles Babbage (anii 1830) ar fi fost prima mașină Turing completă dacă ar fi fost construit în momentul în care a fost proiectat. Babbage a apreciat că mașina era capabilă de calcule extraordinare, inclusiv raționament logic primitiv, dar nu a afirmat că vreo altă mașină nu ar putea face lucrurile acestea mai bine. Din anii 1830 până în anii 1940, au fost construite și îmbunătățite mașini de calcul mecanice, cum ar fi sumatoarele și multiplicatoarele, dar acestea nu puteau efectua o ramificare condiționată și, prin urmare, nu erau Turing-complete.

La sfârșitul secolului al XIX-lea, Leopold Kronecker a formulat noțiunile de calculabilitate, definind funcții recursive primitive. Aceste funcții pot fi calculate prin calcul mecanic, dar nu sunt suficiente pentru a realiza un calculator universal, deoarece instrucțiunile care le calculează nu permit o buclă infinită. La începutul secolului al XX-lea, David Hilbert a condus un program de axiomatizare a întregii matematici cu axiome precise și reguli logice precise de deducție care puteau fi efectuate de o mașină. Curând a devenit clar că un set mic de reguli de deducție este suficient pentru a produce consecințele oricărui set de axiome. Kurt Gödel a demonstrat în 1930 că aceste reguli sunt suficiente pentru a produce orice teoremă.

Noțiunea propriu-zisă de calcul a fost izolată la scurt timp după aceea, începând cu teorema de incompletitudine a lui Gödel. Această teoremă a arătat că sistemele de axiome erau limitate atunci când se raționa despre calculul care le deduce teoremele. Church și Turing au demonstrat independent că Entscheidungsproblem a lui Hilbert (problema deciziei) era nerezolvabilă,[9] identificând astfel nucleul computațional al teoremei incompletitudinii. Această lucrare, împreună cu munca lui Gödel în domeniul funcțiilor general recursive, a stabilit că există seturi de instrucțiuni simple care, atunci când sunt puse împreună, sunt capabile să producă orice calcul. Lucrarea lui Gödel a arătat că noțiunea de calcul este în esență unică.

În 1941, Konrad Zuse a finalizat calculatorul Z3 într-o vreme când nu era familiarizat cu lucrările lui Turing despre calculabilitate. Z3 nu avea, în speță, facilități dedicate saltului condiționat, ceea ce-l făcea să nu fie Turing complet. În 1998, Rojas a demonstrat însă că Z3 era capabil să simuleze salturi condiționate și, prin urmare, era Turing-complet în teorie. Pentru a realiza aceasta însă, programul său pe bandă trebuia să fie suficient de lung pentru a executa orice cale posibilă prin ambele părți ale fiecărei ramificații.[10]

Primul calculator capabil de ramificare condiționată în practică, și prin urmare Turing-complet în practică, a fost ENIAC din 1946. Calculatorul Z4 al lui Zuse era operațional în 1945, dar tot nu suporta ramificarea condiționată, capabilitate ce i-a fost adăugată în 1950.[11]

Teoria calculabilității

[modificare | modificare sursă]

Teoria calculabilității utilizează modele de calcul pentru a analiza problemele și a determina dacă acestea sunt calculabile și în ce circumstanțe. Primul rezultat al teoriei calculabilității este că există probleme pentru care nu se poate prezice ce va face un sistem (Turing-complet) pe o perioadă de timp arbitrar de lungă.

Exemplul clasic este problema opririi: crearea unui algoritm care primește ca intrare un program într-un limbaj Turing-complet și niște date care să fie furnizate acelui program, și determină dacă programul, operând pe respectivele date de intrare, se va opri în cele din urmă sau va continua la nesfârșit. Este trivială crearea unui algoritm care poate face acest lucru pentru anumite intrări, dar imposibil pentru orice set de date. Pentru orice caracteristică a rezultatului final al programului, nu se poate determina dacă această caracteristică se va menține.

Această imposibilitate pune probleme atunci când se analizează programele de calculator din lumea reală. De exemplu, nu se poate scrie un instrument care să protejeze complet programatorii de scrierea buclelor infinite sau să protejeze utilizatorii de furnizarea de date care să provoace bucle infinite.

În schimb, se poate limita un program la execuția doar pentru o perioadă fixă de timp (timeout) sau se poate limita puterea instrucțiunilor de control al fluxului (de exemplu, oferind doar bucle care iterează peste elementele unui tablou existent). Totuși, o altă teoremă arată că există probleme rezolvabile prin limbaje Turing-complete care nu pot fi rezolvate de niciun limbaj care are doar abilități finite de buclare (adică limbaje care garantează că orice program se va opri în cele din urmă). Deci, orice astfel de limbaj nu este Turing-complet. De exemplu, un limbaj care garantează oprirea și finalizarea programelor nu poate calcula funcția calculabilă produsă de argumentul diagonal al lui Cantor asupra tuturor funcțiilor calculabile din acel limbaj.

Oracolele Turing

[modificare | modificare sursă]

Un calculator cu acces la o bandă infinită de date poate fi mai puternic decât o mașină Turing: de exemplu, banda ar putea conține soluția la problema opririi sau la o altă problemă Turing-indecidabilă. O astfel de bandă infinită de date se numește oracol Turing. Un oracol Turing nu este calculabil (cu probabilitate 1) nici cu date aleatoare, deoarece există doar un număr numărabil de calcule, dar un număr nenumărabil de oracole. Deci, un calculator cu un oracol Turing aleatoriu poate calcula lucruri pe care o mașină Turing nu le poate calcula.

Fizică digitală

[modificare | modificare sursă]

Toate legile fizicii cunoscute au consecințe care pot fi calculate printr-o serie de aproximări pe un calculator digital. O ipoteză numită fizică digitală afirmă că acest lucru nu este o întâmplare, deoarece universul însuși este calculabil pe o mașină Turing universală. Aceasta ar implica faptul că niciun calculator mai puternic decât o mașină Turing universală nu poate fi construit fizic.[12]

Exemple

[modificare | modificare sursă]

Sistemele de calcul (algebre, calcule) care sunt tratate ca sisteme Turing-complete sunt cele destinate studierii informaticii teoretice. Acestea sunt concepute să fie cât mai simple posibil, astfel încât să fie mai ușor de înțeles limitele calculului. Iată câteva:

Cele mai multe limbaje de programare (modelele lor abstracte, poate cu unele construcții particulare care presupun omisiunea memoriei finite), convenționale și neconvenționale, sunt Turing-complete. Printre acestea se numără:

Unele sisteme de rescriere sunt Turing-complete.

Turing-completitudinea este o afirmație abstractă a unei abilități, și nu o prescripție de caracteristici lingvistice specifice utilizate pentru a implementa acea abilitate. Caracteristicile utilizate pentru a obține Turing-completitudinea pot fi destul de diferite; sistemele Fortran folosesc construcții de buclă sau chiar instrucțiuni goto pentru a realiza repetiția; Haskell și Prolog, cărora le lipsește aproape complet buclarea, ar folosi recursivitatea. Majoritatea limbajelor de programare descriu calcule pe arhitecturi von Neumann, care au memorie (RAM și registru) și o unitate de control. Aceste două elemente fac ca această arhitectură să fie Turing-completă. Chiar și limbajele funcționale pure sunt Turing-complete.[15][16]

Turing-completitudinea în limbajul declarativ SQL este implementată prin expresii recursive comune de tabel. Nu este surprinzător faptul că extensiile procedurale ale lui SQL (PLSQL etc.) sunt și ele Turing-complete. Aceasta ilustrează unul dintre motivele pentru care sunt foarte rare limbajele relativ puternice, care nu sunt Turing-complete: cu cât limbajul este inițial mai puternic, cu atât sarcinile la care este aplicat sunt mai complexe și cu atât mai repede lipsa sa de completitudine devine percepută ca dezavantaj, încurajând extinderea sa până când devine Turing-complet.

Calculul lambda netipat este Turing-complet, dar multe calcule lambda tipate, inclusiv Sistemul F, nu sunt. Valoarea sistemelor tipate constă în capacitatea lor de a reprezenta majoritatea programelor de calculator tipice, detectând în același timp mai multe erori.

Regula 110 și Jocul Vieții al lui Conway, ambele automate celulare, sunt Turing-complete.

Completitudine Turing neintenționată

[modificare | modificare sursă]

Unele programe software și jocuri video sunt Turing-complete din întâmplare, adică nu intenționat.

Software:

Jocuri:

Rețele sociale:

Limbaje de calcul:

Biologie:

Limbaje care nu sunt Turing-complete

[modificare | modificare sursă]

Există multe limbaje de calcul care nu sunt Turing-complete. Un astfel de exemplu este mulțimea limbajelor regulate, care sunt generate de expresii regulate și care sunt recunoscute de automatele finite. O extensie mai puternică, dar care tot nu este Turing-completă, a automatelor finite este categoria automatelor cu stivă și a gramaticilor independente de context, care sunt utilizate în mod obișnuit pentru a genera arbori de parsare într-o etapă inițială a compilării programelor. Alte exemple sunt unele dintre primele versiuni ale limbajelor de pixel shader încorporate în extensiile Direct3D și OpenGL.

În limbajele de programare total funcționale, cum ar fi Charity și Epigram, toate funcțiile sunt totale și trebuie să se termine. Charity folosește un sistem de tipuri și construcții de control bazate pe teoria categoriilor, în timp ce Epigram folosește tipuri dependente. Limbajul LOOP este conceput astfel încât să calculeze doar funcțiile care sunt primitiv recursive. Toate acestea calculează fiecare câte o submulțime a totalului funcțiilor calculabile, deoarece mulțimea completă a funcțiilor calculabile nu este calculabil enumerabilă. Deoarece toate funcțiile din aceste limbaje sunt totale, algoritmii pentru mulțimi recursiv enumerabile nu pot fi scriși în aceste limbaje, spre deosebire de mașinile Turing.

Deși calculul lambda (netipat) este Turing-complet, calculul lambda simplu tipat nu este.

Note de completare

[modificare | modificare sursă]
  1. ↑ Calculul Turing-complet este în realitate singura paradigmă pentru teoria ce fundamentează informatica...S-a afirmat că, în prezent, paradigma informatică dominantă poate fi caracterizată teoretic drept calcul Turing-complet, limbaje de programare cuprinzătoare, și practic drept gândire computațională, metodologii de programare cuprinzătoare.[3]

Note bibliografice

[modificare | modificare sursă]
  1. ↑ Tom Stuart (). Understanding Computation: From Simple Machines to Impossible Programs. O'Reilly Media, Inc. p. 209. ISBN 978-1-4493-3011-8. Extract of page 209
  2. ↑ Cristian S Calude (). To Halt Or Not To Halt? That Is The Question. World Scientific. p. 30. ISBN 978-981-12-3229-9. Extract of page 30
  3. ↑ Michaelson, Greg (). „Programming Paradigms, Turing Completeness and Computational Thinking”. The Art, Science, and Engineering of Programming. 4 (3). arXiv:2002.06178 Accesibil gratuit. doi:10.22152/programming-journal.org/2020/4/4.
  4. ↑ Göktürk Üçoluk; Sinan Kalkan (). Introduction to Programming Concepts with Case Studies in Python (ed. illustrated). Springer Science & Business Media. p. 13. ISBN 978-3-7091-1343-1. Extract of page 13
  5. ↑ Ben Goertzel (). The Structure of Intelligence: A New Mathematical Model of Mind (ed. illustrated). Springer Science & Business Media. p. 13. ISBN 978-1-4612-4336-6. Extract of page 13
  6. ↑ Alan Garnham (). Artificial Intelligence: An Introduction. Routledge. p. 164. ISBN 978-1-351-33786-1. Extract of page 164
  7. ↑ Torben Ægidius Mogensen (). Programming Language Design and Implementation. Springer Nature. p. 6. ISBN 978-3-031-11806-7. Extract of page 6
  8. ↑ John R. Woodward (). „Modularity in Genetic Programming”. Genetic Programming: 6th European Conference, EuroGP 2003, Essex, UK, April 14-16, 2003. Proceedings, Volume 6 (ed. illustrated). Springer Science & Business Media. p. 258. doi:10.1007/3-540-36599-0_23. ISBN 978-3-540-00971-9. Extract of page 258
  9. ↑ Hodges, Andrew () [1983], Alan Turing: The Enigma, London: Burnett Books, p. 111, ISBN 0-04-510060-8
  10. ↑ Rojas, Raul (). „How to make Zuse's Z3 a universal computer”. Annals of the History of Computing. 20 (3): 51–54. doi:10.1109/85.707574.
  11. ↑ Rojas, Raúl (). „Konrad Zuse und der bedingte Sprung” [Konrad Zuse and the conditional jump]. Informatik-Spektrum (în germană). 37 (1): 50–53. doi:10.1007/s00287-013-0717-9. ISSN 0170-6012.
  12. ↑ Schmidhuber, Jürgen (), Freksa, Christian; Jantzen, Matthias; Valk, Rüdiger, ed., „A computer scientist's view of life, the universe, and everything”, Foundations of Computer Science: Potential — Theory — Cognition, Lecture Notes in Computer Science (în engleză), Berlin, Heidelberg: Springer, 1337, pp. 201–208, arXiv:quant-ph/9904050 Accesibil gratuit, doi:10.1007/bfb0052088, ISBN 978-3-540-69640-7, accesat în
  13. ↑ Dfetter; Breinbaas (). „Cyclic Tag System”. PostgreSQL wiki. Accesat în .[nefuncțională – arhivă]
  14. ↑ Lyons, Bob (). „Universal Turing Machine in XSLT”. B2B Integration Solutions from Unidex. Arhivat din original la . Accesat în .
  15. ↑ Boyer, Robert S.; Moore, J. Strother (mai 1983). A Mechanical Proof of the Turing Completeness of Pure Lisp (PDF) (Raport tehnic). Arhivat din original (PDF) la .
  16. ↑ Rauber, Thomas; Rünger, Gudula (). Parallel programming: for multicore and cluster systems (ed. 2nd). Springer. ISBN 9783642378010.
  17. ↑ „Announcing LAMBDA: Turn Excel formulas into custom functions”. TECHCOMMUNITY.MICROSOFT.COM (în engleză). . Accesat în .
  18. ↑ Cedotal, Andrew (). „Man Uses World's Most Difficult Computer Game to Create … A Working Turing Machine”. The Mary Sue. Arhivat din original la . Accesat în .
  19. ↑ Plunkett, Luke (). „Cities: Skylines Map Becomes A Poop-Powered Computer”. Kotaku. Accesat în .
  20. ↑ Caldwell, Brendan (). „Opus Magnum player makes an alchemical computer”. Rock Paper Shotgun. Accesat în .
  21. ↑ Crider, Michael. „This 8-bit processor built in Minecraft can run its own games”. PCWorld (în engleză). Accesat în .[nefuncțională – arhivă]
  22. ↑ Churchill, Alex; Biderman, Stella; Herrick, Austin (). Magic: The Gathering Is Turing Complete (PDF). 10th International Conference on Fun with Algorithms. Arhivat din original (PDF) la . Accesat în .
  23. ↑ Ouellette, Jennifer (). „It's possible to build a Turing machine within Magic: The Gathering”. Ars Technica. Accesat în .
  24. ↑ Kaye, Richard (). „Infinite versions of minesweeper are Turing complete” (PDF). Arhivat din original (PDF) la . Accesat în .
  25. ↑ „Habbo's Twitter thread on the implementation of a Turing machine inside the game”. . Accesat în .
  26. ↑ Meyers, Scott (Scott Douglas) (). Effective C++ : 55 specific ways to improve your programs and designs (ed. 3rd). Upper Saddle River, NJ: Addison-Wesley. ISBN 0321334876. OCLC 60425273.
  27. ↑ A 27th IOCCC Winner

    Carlini, Nicolas; Barresi, Antonio; Payer, Mathias; Wagner, David; Gross, Thomas R. (august 2015). „Control-flow bending: on the effectiveness of control-flow integrity”. Proceedings of the 24th USENIX Conference on Security Symposium. pp. 161–176. ISBN 9781931971232.
  28. ↑ Dabler, Ryan (). „TypeScript and Turing Completeness”. ITNEXT. LINKIT. Accesat în .
  29. ↑ Dolan, Stephen. „mov is Turing-complete” (PDF). stedolan.net. Arhivat din original (PDF) la . Accesat în .
  30. ↑ Williams, Al (). „One Instruction To Rule Them All: C Compiler Emits Only MOV”. Hackaday. Accesat în .
  31. ↑ Break Me00 The MoVfuscator Turning mov into a soul crushing RE nightmare Christopher Domas (în engleză), , accesat în
  32. ↑ Shah, Shalin; Wee, Jasmine; Song, Tianqi; Ceze, Luis; Strauss, Karin; Chen, Yuan-Jyue; Reif, John (). „Using Strand Displacing Polymerase To Program Chemical Reaction Networks”. Journal of the American Chemical Society. 142 (21): 9587–9593. doi:10.1021/jacs.0c02240. ISSN 0002-7863. PMID 32364723.
  33. ↑ Chen, Yuan-Jyue; Dalchau, Neil; Srinivas, Niranjan; Phillips, Andrew; Cardelli, Luca; Soloveichik, David; Seelig, Georg (octombrie 2013). „Programmable chemical controllers made from DNA”. Nature Nanotechnology (în engleză). 8 (10): 755–762. Bibcode:2013NatNa...8..755C. doi:10.1038/nnano.2013.189. ISSN 1748-3395. PMC 4150546 Accesibil gratuit. PMID 24077029.
  34. ↑ Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik; Soloveichik, David (). „Enzyme-free nucleic acid dynamical systems”. Science (în engleză). 358 (6369): eaal2052. doi:10.1126/science.aal2052. ISSN 0036-8075. PMID 29242317.
  35. ↑ Soloveichik, David; Seelig, Georg; Winfree, Erik (). „DNA as a universal substrate for chemical kinetics”. Proceedings of the National Academy of Sciences (în engleză). 107 (12): 5393–5398. Bibcode:2010PNAS..107.5393S. doi:10.1073/pnas.0909380107. ISSN 0027-8424. PMC 2851759 Accesibil gratuit. PMID 20203007.
  36. ↑ Shapiro, Ehud (). „A Mechanical Turing Machine: Blueprint for a Biomolecular Computer”. Interface Focus. Weizmann Institute of Science. 2 (4): 497–503. doi:10.1098/rsfs.2011.0118. PMC 3363030 Accesibil gratuit. PMID 22649583. Arhivat din original la . Accesat în .

Lectură suplimentară

[modificare | modificare sursă]

 

Adus de la https://ro.wikipedia.org/w/index.php?title=Turing-completitudine&oldid=17572163