Teoria computației

Reprezentare artistică a unei mașini Turing. Mașinile Turing sunt frecvent utilizate ca modele teoretice de calcul.

În informatica teoretică^⁠(d) și în matematică, teoria computației este ramura care se ocupă cu cât de eficient pot fi rezolvate problemele pe un model de calcul^⁠(d), folosind un algoritm. Domeniul este împărțit în trei ramuri majore: teoria limbajelor formale și automatelor, teoria calculabilității și teoria complexității, care sunt legate de întrebarea: „care sunt capabilitățile fundamentale și limitările calculatoarelor?”.

Pentru a efectua un studiu riguros al computației, informaticienii lucrează cu o abstracție matematică a calculatorului, numită model de calcul^⁠(d). Există mai multe modele în uz, dar cel mai frecvent examinat este o mașină Turing. Informaticienii studiază mașina Turing, deoarece este simplu de formulat, poate fi analizată și utilizată pentru a demonstra rezultatele, și pentru că ea reprezintă ceea ce mulți consideră a fi cel mai puternic posibil model de calcul „rezonabil” (a se vedea teza Church–Turing). Capacitatea potențial infinită a memoriei ar părea o cerință nerealizabilă, dar orice problemă decidabilă^⁠(d) rezolvată de către o mașină Turing va necesita întotdeauna doar o cantitate finită de memorie. Deci, în principiu, orice problemă care poate fi rezolvată (decisă) de către o mașină Turing poate fi rezolvată de către un computer care are o cantitate finită de memorie.

Istorie

Teoria computației poate fi considerată crearea de modele de toate tipurile în domeniul informaticii. Prin urmare, se utilizează matematica și logica. În ultimul secol, a devenit o disciplină academică independentă și separată de matematică.

Unii reprezentanți ai teoriei computației au fost Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, John von Neumann și Claude Shannon.

Ramuri

Teoria automatelor

Gramatică	Limbaje	Automate	Reguli de producție (constrângeri)
Tip 0	Recursiv enumerabile⁠(d)	Mașină Turing	$\alpha \rightarrow \beta$ (fără restricții)
Tip 1	Dependente de context⁠(d)	Mașină Turing nedeterministă liniar mărginită⁠(d)	$\alpha A\beta \rightarrow \alpha \gamma \beta$
Tip 2	Independente de context⁠(d)	Automatul cu stivă⁠(d) nedeterminist	$A\rightarrow \gamma$
Tip 3	Regulate⁠(d)	Automatul finit	$A\rightarrow a$ și $A\rightarrow aB$

Teoria automatelor este studiul mașinilor abstracte (sau, mai corect, mașinilor sau sistemelor „matematice” abstracte) și problemelor de calcul care pot fi rezolvate cu ajutorul acestor mașini. Aceste mașini abstracte sunt numite „automate”, cuvânt care provine de la termenul grecesc (Αυτόματα), ceea ce înseamnă că ceva face ceva de la sine. Teoria automatelor este, de asemenea, strâns legată cea a limbajelor formale, întrucât automatele sunt adesea clasificate în funcție de clasa de limbaje formale pe care sunt în stare să o recunoască. Un automat poate fi o reprezentare finită a unui limbaj formal care poate fi o mulțime infinită. Automatele sunt folosite ca modele teoretice pentru mașinile de calcul, și sunt folosite pentru demonstrații ale calculabilității.

Teoria limbajelor formale

Incluziunea mulțimilor descrisă de ierarhia Chomsky

Teoria limbajelor este o ramură a matematicii care se ocupă cu descrierea limbajelor ca mulțimi de operațiuni peste un alfabet. Ea este strâns legată de teoria automatelor, întrucât automatele sunt folosite pentru a genera și a recunoaște limbaje formale. Există mai multe clase de limbaje formale, fiecare permițând specificații mai complexe de limbaj decât cea dinainte, de unde structurarea lor în ierarhia Chomsky, și fiecare corespunzând unei clase de automate care o recunoaște. Pentru că automatele sunt folosite ca modele de calcul, limbajele formale sunt modul preferat de specificare pentru orice problemă care trebuie să fie calculată.

Teoria calculabilității

Teoria calculabilității se ocupă în principal cu întrebarea dacă o problemă este rezolvabilă de un calculator. Afirmația că problema opririi^⁠(d) nu poate fi rezolvată de către o mașină Turing este unul dintre cele mai importante rezultate din teoria calculabilității, un exemplu de problemă concretă, care este atât de ușor de formulat, dar imposibil de rezolvat folosind o mașină Turing. Mare parte din teoria calculabilității se bazează pe rezultatul problemei opririi.

Un alt pas important în teoria calculabilității a fost teorema lui Rice^⁠(d), care prevede că pentru toate proprietățile netriviale ale funcțiilor parțiale, este indecidabil^⁠(d) dacă o mașină Turing calculează o funcție parțială cu acea proprietate.

Teoria calculabilității este strâns legată de ramura logicii matematice denumită teoria recursivității, care elimină restricția de a studia numai modele de calcul, reductibile la modelul Turing. Mulți matematicieni și teoreticieni ai calculabilității care studiază teoria recursivității o denumesc și pe ea „teoria calculabilității”.

Teoria complexității computaționale

O reprezentare a relației dintre clasele de complexitate

Teoria complexității consideră nu numai dacă o problemă poate fi rezolvată de un calculator, ci și cât de eficient poate fi ea rezolvată. Sunt analizate două aspecte majore: complexitatea în timp și complexitatea în spațiu, adică de câți pași este nevoie pentru a efectua un calcul și, respectiv, de cât de multă memorie este necesară pentru a efectua acest calcul.

Pentru a analiza de cât timp și spațiu are nevoie un anumit algoritm, informaticienii exprimă timpul și spațiul necesar pentru a rezolva problema în funcție de mărimea problemei de la intrare. De exemplu, găsirea unui anumit număr într-o listă lungă de numere devine mai greu pe măsură ce lista de numere crește. Dacă am spune că există n numere în listă, atunci, dacă lista nu este sortată sau indexată în vreun fel, s-ar putea să fie nevoie să se caute fiecare număr, în scopul de a găsi numărul căutat. Se poate spune, deci, că, în scopul de a rezolva această problemă, calculatorul are nevoie să efectueze o serie de pași care crește liniar cu dimensiunea problemei.

Pentru a simplifica această problemă, informaticienii au adoptat notația Big O, care permite compararea funcțiilor într-un mod care garantează că anumite aspecte constructive ale unei mașini fizice pot fi ignorate, expresia fiind relevantă numai pentru comportamentul asimptotic^⁠(d) pe măsură ce problemele devin mai mari. Deci, în exemplul anterior s-ar putea spune că problema necesită $O(n)$ pași pentru a fi rezolvată.

Poate cea mai importantă problemă deschisă în toată informatica este întrebarea dacă o anumită clasă largă de probleme notate NP pot fi rezolvate în mod eficient. Problema P versus NP este una dintre cele șapte probleme ale Premiului Mileniului^⁠(d) declarate de Clay Mathematics Institute^⁠(d) în anul 2000. Descrierea oficială a problemei Arhivat în 4 septembrie 2015, la Wayback Machine. a fost făcută de laureatul premiului Turing, Stephen Cook.

Modele de calcul

În afară de mașina Turing, există și alte modele de calcul echivalente.

Calculul Lambda^⁠(d)

Un calcul constă dintr-o expresie lambda inițială (sau două, dacă se dorește separarea funcției de intrare), plus o secvență finită de termeni lambda, fiecare dedus din cel anterior termen printr-o aplicare a unei reduceri Beta.

Logica combinatorică^⁠(d)

este un concept care are multe similitudini cu calculul calculul $\lambda$, dar există și diferențe importante (de exemplu, combinatorul de punct fix Y are formă normală în logica combinatorică, dar nu și în calculul $\lambda$). Logica combinatorică a fost dezvoltată cu mari ambiții: de a înțelege natura paradoxurilor, de a face bazele matematicii mai economice (conceptual), de a elimina noțiunea de variabilă (clarificând astfel rolul acestora în matematică).

Funcțiile μ-recursive^⁠(d)

un calcul constă dintr-o funcție miu-recursivă, adică șirul său de definiție, orice valoare de intrare(e) și un șir de funcții recursive care apar în șirul de definiție cu intrări și ieșiri. Astfel, dacă în șirul de definiție al unei funcții recursive $f(x)$ apar funcțiile $g(x)$ și $h(x,y)$, atunci ar putea apărea termeni de forma „g(5)=7” sau „h(3,2)=10”. Fiecare element din acest șir trebuie să fie o aplicație a unei funcții de bază sau să rezulte din elementele menționate de mai sus, prin utilizarea compunerii^⁠(d), recursivității primitive^⁠(d) sau μ-recursivității^⁠(d). De exemplu, dacă $f(x)=h(x,g(x))$, atunci pentru a apărea „f(5)=3”, trebuie să apară mai întâi termeni ca „g(5)=6” și „h(5,6)=3”. Calculul se termină doar dacă ultimul termen dă valoarea funcției recursive aplicată asupra intrării.

Algoritm Markov^⁠(d)

un sistem de rescriere a șirurilor^⁠(d) care folosește reguli ca cele gramaticale pentru a funcționa pe șiruri^⁠(d) de simboluri.

Mașină cu regiștri^⁠(d)

este o idealizare a unui calculator, de interes teoretic. Există mai multe variante. În cele mai multe dintre ele, fiecare registru poate reține un număr natural (de dimensiuni nelimitate), iar instrucțiunile sunt simple (și puține la număr), de exemplu, există doar decrementarea (combinată cu saltul condiționat) și incrementarea (și oprirea). Lipsa unui suport de stocare externă finit (sau în creștere dinamică; așa cum se observă la mașina Turing) poate fi înțeleasă prin înlocuirea rolului său cu tehnici de numerotare Gödel^⁠(d): faptul că fiecare registru reține un număr natural permite posibilitatea de a reprezenta ceva complicat (de exemplu, un șir sau o matrice etc.) printr-un număr natural mare corespunzător — lipsa de ambiguitate atât a reprezentării cât și a interpretării poate fi stabilită prin bazele acestor tehnici din teoria numerelor.

În plus față de modelele de calcul generale, există și unele modele de calcul mai simple, utile pentru aplicații speciale, restricționate. Expresiile regulate, de exemplu, specifică modele de șiruri de caractere în mai multe contexte, de la software-uri de productivitate la birou și până la limbaje de programare. Un alt formalism matematic echivalent cu expresiile regulate, automatele finite, este utilizat în proiectarea circuitelor și în unele tipuri de rezolvare a problemelor. Gramaticile independente de context^⁠(d) specifică sintaxa limbajelor de programare. Automatele nedeterministe cu stivă^⁠(d) sunt un alt formalism echivalent cu gramaticile independente de context. Funcțiile recursive primitive^⁠(d) sunt o subclasă a funcțiilor recursive.

Diferitele modele de calcul au capacitatea de a îndeplini diferite sarcini. O modalitate de a măsura puterea unui model de calcul este de a studia clasa de limbaje formale pe care o poate genera modelul; într-un asemenea mod se obține ierarhia Chomsky.

Lectură suplimentară

Manualele pentru informaticieni

(Există mai multe manuale în acest domeniu; această listă este inerent incompletă.)

• Hopcroft, John E., și Jeffrey D. Ullman (2006). Introducere în teoria automatelor, a limbajelor formale și a calculabilitatății. 3rd ed Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9 Una dintre lucrările standard de referință în domeniu.
• Michael Sipser^⁠(d) (2013). Introduction to the Theory of Computation (ed. 3rd). Cengage Learning. ISBN 978-1-133-18779-0. 
• Eitan Gurari (1989). An Introduction to the Theory of Computation. Computer Science Press. ISBN 0-7167-8182-4. Arhivat din original la 7 ianuarie 2007. Accesat în 26 mai 2017. 
• Hein, James L. (1996) Theory of Computation. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1 O introducere sumară în domeniu, adecvată pentru studenții de anul al doilea la informatică.
• Taylor, R. Grigorie (1998). Models of Computation and Formal Languages. New York: Oxford University Press. ISBN 978-0-19-510983-2 Un manual neobișnuit de ușor de citit, adecvat pentru studenții din ultimii ani ai ciclului de diplomă sau licență sau pentru cei care încep studiile postuniversitare.
• Lewis, F. D. (2007). Essentials of theoretical computer science Un manual care acoperă subiecte de limbaje formale, automate și gramatici. Accentul pare a fi pe prezentarea unei imagini de ansamblu a rezultatelor și a aplicațiilor lor, mai degrabă decât pe furnizarea de demonstrații ale rezultatelor.
• Martin Davis^⁠(d), Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, ed. a 2, Academic Press, 1994, ISBN 0-12-206382-1. Acoperă o gamă mai largă de subiecte decât cele mai multe cărți introductive, între care semantica programelor și teoria cuantificării. Destinată studenților din ciclurile postuniversitare.

Cărți de teoria computabilității din perspectivă matematică (mai largă)

• Hartley Rogers Jr (1987). Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1
• S. Barry Cooper^⁠(d) (2004). Computability Theory. Chapman and Hall/CRC. ISBN 1-58488-237-9.  .
• Carl H. Smith, A recursive introduction to the theory of computation, Springer, 1994, ISBN 0-387-94332-3. Un manual scurt potrivit pentru studenții la informatică din ciclul postuniversitar.

Perspectivă istorică

• Richard L. Epstein and Walter A. Carnielli (2000). Computability: Computable Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (2nd ed.). Wadsworth/Thomson Learning. ISBN 0-534-54644-7.  .

Legături externe

• Theory of Computation la MIT
• Theory of Computation la Harvard
• Logica computabilității Arhivat în 11 aprilie 2011, la Wayback Machine. - o teoria a calculului interactiv. Principala resursă web pe acest subiect.