Î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 Extract of page 209 Extract of page 30 (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.
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. Extract of page 13 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ă. Extract of page 13 Extract of page 164
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. Extract of page 6 Extract of page 258
Utilizare în afara matematicii Î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 Î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 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ă a lui Hilbert (problema deciziei) era nerezolvabilă, 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.
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.
Teoria calculabilității 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 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ă 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.
Exemple 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:
Teoria automatelor Gramaticile formale (generatoare de limbaje) Limbajele formale (mașini de recunoaștere a limbajelor) Calculul lambda Mașini post-Turing Calculul de proces
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ă:
Toate limbajele de uz general utilizate pe scară largă. Limbaje de programare procedurale precum C, Pascal. Limbaje orientate pe obiecte, cum ar fi Java, Smalltalk sau C#. Limbaje multi-paradigmă precum Ada, C++, Common Lisp, Fortran, JavaScript, Object Pascal, Perl, Python, R. Majoritatea limbajelor folosesc paradigme mai puțin comune: Limbaje funcționale precum Lisp și Haskell. Limbaje de programare logică, cum ar fi Prolog. Procesoare de macrouri de uz general, cum ar fi m4. Limbaje declarative precum SQL și XSLT. VHDL și alte limbaje de descriere a hardware-ului.