0 teoría de la computación
Rama de la informática y las matemáticas que se ocupa de estudiar si los problemas de cómputo se pueden resolver eficientemente en una computadora y la forma de hacerlo. Se han establecido diferentes aproximaciones equivalentes en expresividad computacional por Alan Turing y Alonzo Church, como son los modelos de la máquina de Turing, las funciones recursivas, y el cálculo Lambda. La conjetura de Church-Turing asume que las computadoras son equivalentes en capacidad de cómputo a cualquiera de los tres modelos mencionados. Gracias a tal conjetura, todo problema de cómputo que sea resoluble en una máquina de Turing, se considera que también lo será en una computadora, y viceversa. Mediante esta equivalencia se ha determinado que existen cálculos que no pueden ser resueltos en un tiempo razonable en ninguna computadora imaginable. Es importante conocer la complejidad computacional de un algoritmo, pues ésta determinará la aplicabilidad del mismo.
La teoría de la computación se divide en tres ramas principales: la teoría de la computabilidad, la teoría de la complejidad y la teoría de los lenguajes y gramáticas formales.
- 1963 julio 1
- Arranca el Proyecto MAC en el MIT, pionero en investigación en diferentes ramas de la informática.
