Computacion

* 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 resolvertodos 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).
Entre los modelos de cómputo más recientes se encuentran loslenguajes de programación, que también han mostrado ser equivalentes a los modelos anteriores; esto es una fuerte evidencia de la conjetura de Church-Turing, de que todo algoritmo habido y por haber sepuede simular en una máquina de Turing, o equivalentemente, usando funciones recursivas.
* Principales Subramas:

* Teoría de autómatas: Esta teoría provee modelos matemáticos que formalizan elconcepto de computadora o algoritmo de manera suficientemente simplificada y general para que se puedan analizar sus capacidades y limitaciones. Los tres principales modelos son los autómatasfinitos, autómatas con pila y máquinas de Turing, cada uno con sus variantes deterministas y no deterministas.

* Teoría de la computabilidad: Esta teoría explora los límites de la posibilidad desolucionar problemas mediante algoritmos. Gran parte de las ciencias computacionales están dedicadas a resolver problemas de forma algorítmica, de manera que el descubrimiento de problemas imposibles es...