Teoría da computación
From Wikipedia, the free encyclopedia
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.