Teoria computacional

Teoría de la computación
La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas

Historia

La teoría de la computación comienzapropiamente a principios del siglo XX, poco antes que las computadoras electrónicas fuesen inventadas. En esta época varios matemáticos se preguntaban si existía un método universal para resolver todos los problemas matemáticos. Para ello debían desarrollar la noción precisa de método para resolver problemas, es decir, la definición formal de algoritmo.
Algunos de estos modelos formales fueronpropuestos por precursores como Alonzo Church (cálculo Lambda), Kurt Gödel (funciones recursivas) y Alan Turing (máquina de Turing). Se ha mostrado que estos modelos son equivalentes en el sentido de que pueden simular los mismos algoritmos, aunque lo hagan de maneras diferentes. Entre los modelos de cómputo más recientes se encuentran los lenguajes de programación, que también han mostrado serequivalentes a los modelos anteriores; esto es una fuerte evidencia de la conjetura de Church-Turing, de que todo algoritmo habido y por haber se puede simular en una máquina de Turing, o equivalentemente, usando funciones recursivas. En 2007 Nachum Dershowitz y Yuri Gurevich publicaron una demostración de esta conjetura basándose en cierta axiomatización de algoritmos.[1]
Uno de los primeros resultadosde esta teoría fue la existencia de problemas imposibles de resolver algoritmicamente, siendo el problema de la parada el más famoso de ellos. Para 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 problemasresolubles en teoría eran imposibles en la práctica, puesto que dichas soluciones necesitaban cantidades irrealistas de tiempo o memoria para poderse encontrar.

Teoría de autómatas

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. Algunos de estosmodelos juegan un papel central en varias aplicaciones de las ciencias de la computación, incluyendo procesamiento de texto, compiladores, diseño de hardware e inteligencia artificial.
Los tres principales modelos son los autómatas finitos, autómatas con pila y máquinas de Turing, cada uno con sus variantes deterministas y no deterministas. Los autómatas finitos son buenos modelos de computadorasque tienen una cantidad limitada de memoria, los autómatas con pila modelan los que tienen gran cantidad de memoria pero que solo pueden manipularla a manera de pila (el último dato almacenado es el siguiente leído), y las máquinas de Turing modelan las computadoras que tienen una gran cantidad de memoria almacenada en una cinta. Estos autómatas están estrechamente relacionados con la teoría delenguajes formales; cada autómata es equivalente a una gramática formal, lo que permite reinterpretar la jerarquía de Chomsky en términos de autómatas.
Existen muchos otros tipos de autómatas como las máquinas de acceso aleatorio, autómatas celulares, máquinas ábaco y las máquinas de estado abstracto; sin embargo en todos los casos se ha mostrado que estos modelos no son más generales que lamáquina de Turing, pues la máquina de Turing tiene la capacidad de simular cada uno de estos autómatas. Esto da lugar a que se piense en la máquina de Turing como el modelo universal de computadora.

Teoría de la computabilidad

Esta teoría explora los límites de la posibilidad de solucionar problemas mediante algoritmos. Gran parte de las ciencias computacionales están dedicadas a resolver...