La teoría de la computación es la formalización matemática de los algoritmos.
Tradicionalmente se estructura en:
-
Autómatas finitos y lenguajes regulares.
Se aplican en la síntesis de sistemas digitales, en el diseño de los analizadores
léxicos de los compiladores e intérpretes, patrones de búsqueda, flujos de trabajo en entornos colaborativos....
-
Autómatas de pila y lenguajes independientes del contexto.
Se aplica en el diseño de lenguajes de programación y sus compiladores e intérpretes
-
Máquinas de Turing y cálculo lambda.
Máquinas conceptuales creadas para demostrar los límites de los computadores
-
Decidibilidad de problemas.
Utilizando las Máquinas de Turing y otros formalismos, se describen herramientas para
demostrar los límites de los computadores.
-
Computabilidad de problemas.
Aunque un problema sea computable, la realidad es que si su complejidad es
exponencial, no habrá un computador (Máquina de Turing) capaz de resolverlo en un tiempo razonable.
-
Autómatas finitos y lenguajes regulares
(html)