Teoría de la computación
De Wikipedia, la enciclopedia encyclopedia
La teoría de la computación o teoría de la informática es un conjunto de conocimientos racionales y sistematizados que se centran en el estudio de la abstracción de los procesos, con el fin de reproducirlos con ayuda de sistemas formales; es decir, a través de símbolos y reglas lógicas. La teoría de la computación permite modelar procesos dentro de las limitaciones de dispositivos que procesan información y que efectúan cálculos; como, por ejemplo, el ordenador. Para ello, se apoya en la teoría de autómatas, a fin de simular y estandarizar dichos procesos, así como para formalizar los problemas y darles solución.[1]
Este artículo o sección necesita ser wikificado, por favor, edítalo para que cumpla con las convenciones de estilo. |
Para realizar un estudio riguroso de la computación, los informáticos trabajan con una abstracción matemática de los ordenadores llamada modelo de computación. Hay varios modelos en uso, pero el más comúnmente examinado es la máquina de Turing.[2] Los informáticos estudian la máquina de Turing porque es sencilla de formular, se puede analizar y utilizar para demostrar resultados, y porque representa lo que muchos consideran el modelo "razonable" de computación más potente posible (véase tesis Church-Turing).[3] Podría parecer que la capacidad de memoria potencialmente infinita es un atributo irrealizable, pero cualquier problema decidible[4] resuelto por una máquina de Turing siempre requerirá sólo una cantidad finita de memoria. Así que, en principio, cualquier problema que pueda ser resuelto (decidido) por una máquina de Turing puede ser resuelto por un ordenador que tenga una cantidad finita de memoria.