Teoría de la computación

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.Hay varios modelos en uso, pero el más comúnmente examinado es la máquina de Turing.Esta teoría provee modelos matemáticos que formalizan el concepto de computadora o algoritmo de manera suficientemente simplificada y general para que se puedan analizar sus capacidades y limitaciones.La herramienta principal para lograr estas clasificaciones es el concepto de reducibilidad: Un problemaEstá estrechamente relacionada con la teoría de autómatas, ya que éstos se utilizan para generar y reconocer lenguajes formales.Dado que los autómatas se utilizan como modelos para la computación, los lenguajes formales son el modo preferido de especificación para cualquier problema que deba ser computado.Esta teoría tiene aplicación en casi todas las áreas de conocimiento donde se desee resolver un problema computacionalmente, porque los investigadores no solo desean utilizar un método para resolver un problema, sino utilizar el más rápido.Para analizar cuánto tiempo y espacio requiere un algoritmo determinado, los informáticos expresan el tiempo o el espacio necesarios para resolver el problema en función del tamaño del problema de entrada.Para simplificar este problema, los informáticos han adoptado la notación Big O, que permite comparar funciones de forma que no sea necesario considerar aspectos particulares de la construcción de una máquina, sino sólo el comportamiento asintótico a medida que los problemas se hacen grandes.Así, en nuestro ejemplo anterior, podríamos decir que el problema requierePara estos problemas no existe ni existirá ningún algoritmo que los pueda resolver, no importando la cantidad de tiempo o memoria se disponga en una computadora.Asimismo, con la llegada de las computadoras modernas se constató que algunos problemas resolubles en teoría eran imposibles en la práctica, puesto que dichas soluciones necesitaban cantidades irrealistas de tiempo o memoria para poderse encontrar.(Hay muchos libros de texto en este campo; esta lista es necesariamente incompleta).