Teoría da computación

Representación artística dunha máquina de Turing, empregadas adoito como modelos teóricos para a computación

En informática teórica e matemáticas, a teoría da computación é a rama que estuda como de eficientemente poden resolverse os problemas nun modelo de computación, empregando un algoritmo. O campo divídese en tres áreas principais: a teoría e linguaxe de autómatas, a teoría da computabilidade e a teoría da complexidade computacional, que están ligadas pola pregunta: "cales son as capacidades fundamentais e as limitacións das computadoras?".^[1]

Para establecer un estudo rigoroso sobre a computación, os científicos computacionais traballan cunha abstracción matemática de computadoras denominada modelo de computación. Existen varios modelos en uso, mais o máis comunmente examinado é a máquina de Turing.^[2] Os científicos computacionais estudan a máquina de Turing porque é sinxela de formular, pode ser analizada e empregada para demostrar resultados e representa o que a maioría considera o posible modelo "razoable" máis poderoso de computación (tese de Church-Turing).^[3] Pode parecer que a capacidade de memoria potencialmente infinita é un atributo irrealizable, pero calquera problema decidible^[4] resolto mediante unha máquina de Turing requirirá só unha cantidade finita de memoria. Así, en principio, calquera problema que se poida resolver (decidir) mediante unha máquina de Turing pode ser resolto mediante unha computadora cunha cantidade finita de memoria.

Historia

A teoría da computación pode considerarse como a creación de modelos de todas as clases no campo da informática. Polo tanto, emprégase a lóxica matemática. No século XX converteuse nunha disciplina académica diferente e separada das matemáticas.

Algúns pioneiros neste campo foron Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, John von Neumann e Claude Shannon.

Ramas

Teoría de autómatas

A teoría de autómatas é o estudo de máquinas abstractas e problemas de computación que poden resolverse mediante as máquinas abstractas chamadas autómatas. O vocábulo "autómata" procede da palabra grega Αυτόματα, que significa que algo está facendo algo por el mesmo. A teoría de autómatas está moi relacionada coa teoría da linguaxe formal,^[5] xa que os autómatas adoitan clasificarse segundo a clase de linguaxe formal que son capaces de recoñecer.

Teoría da computabilidade

A teoría da computabilidade estuda principalmente que alcance dun problema é resoluble cunha computadora. A afirmación de que o problema da parada non pode ser resolto por unha máquina de Turing^[6] é un dos máis importantes resultados da teoría da computabilidade, xa que é un exemplo dun problema concreto que é simple de formular e imposible de resolver cunha máquina de Turing.

Outro chanzo importante na teoría da computabilidade foi o teorema de Rica, que afirma que para todas as propiedades non triviais das funcións parciais, é indecidible se unha máquina de Turing computa unha función parcial con esa propiedade.^[7]

A teoría da computabilidade está moi relacionada coa rama da lóxica matemática chamada teoría da recursión, que suprime a restrición de estudar só modelos de computación reducibles ao modelo de Turing.^[8]

Teoría da complexidade computacional

Representación da relación entre clases de complexidade

A teoría da complexidade considera non só se un problema pode ou non ser resolto nunha computadora, senón como de eficientemente pode ser resolto. Considéranse dous aspectos principais: a complexidade do tempo e a complexidade do espazo, que son respectivamente cantos pasos son necesarios para establecer unha computación e canta memoria se requira para realizala.

Notas

1. Michael Sipser (2013). Introduction to the Theory of Computation 3rd. Cengage Learning. ISBN 978-1-133-18779-0. central areas of the theory of computation: automata, computability, and complexity. (Page 1) 
2. Andrew Hodges (2012). Alan Turing: The Enigma (THE CENTENARY EDITION). Princeton University Press. ISBN 978-0-691-15564-7. 
3. Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. 
4. Donald Monk (1976). Mathematical Logic. Springer-Verlag. ISBN 9780387901701. 
5. Hopcroft, John E. and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9. 
6. Turing, A. M. (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. s2-42 (1): 230–265. ISSN 0024-6115. doi:10.1112/plms/s2-42.1.230. Arquivado dende o orixinal o 21 de xaneiro de 2022. Consultado o 20 de marzo de 2022. 
7. Henry Gordon Rice (1953). "Classes of Recursively Enumerable Sets and Their Decision Problems". Transactions of the American Mathematical Society (American Mathematical Society) 74 (2): 358–366. JSTOR 1990888. doi:10.2307/1990888. 
8. Martin Davis (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications. ISBN 978-0486432281. 

Véxase tamén

Bibliografía

• Hopcroft, John E., e Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9
• Michael Sipser (2013). Introduction to the Theory of Computation (3rd ed.). 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. Arquivado dende o orixinal o 07 de xaneiro de 2007. Consultado o 18 de xullo de 2017. 
• Hein, James L. (1996) Theory of Computation. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1
• Taylor, R. Gregory (1998). Models of Computation and Formal Languages. Nova York: Oxford University Press. ISBN 978-0-19-510983-2
• Lewis, F. D. (2007). Essentials of theoretical computer science
• Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0-12-206382-1

Outros artigos

• Teoría da computabilidade

Ligazóns externas

• Theory of Computation no MIT
• Theory of Computation en Harvard
• Computability Logic