Introducción
Este curso es una primera introducción a dos de las áreas centrales de la Teoría de la Computación (TC): la teoría de los autómatas y lenguajes formales y la teoría de la computabilidad.1
La Teoría de la Computación es una área de investigación activa y con muchas interconexiones con Informática, Matemática, Lógica, y Filosofía. Por ejemplo, con el Análisis de Algoritmos, Computación cuántica, Criptografía, … Recientemente, ha sido argumentado también que la Teoría de la Computación, sus conceptos y metodologías son también muy relevantes en ámbitos como Biología molecular, Ecología y Evolución, Neurociencias, Física cuántica, Economía, y Ciencias Sociales.2
Las preguntas motivadoras detrás de la Teoría de la Computación son las siguientes:
¿Cuáles son las capacidades (y las limitaciones) de los ordenadores?
¿Qué significa en realidad computación?
La Teoría de la Computación nace a los alrededores de los años 1930-1940 con el trabajo de matemáticos y lógicos como Kurt Gödel, Alan Turing, o Alonzo Church (entre otros) que descubren que hay problemas (interesantes) que no se pueden resolver con un ordenador. Por ejemplo:
- Decidir si una afirmación matemática es cierta o falsa.
- Decidir si un programa con un dado input para o no.
La teoría de la calculabilidad, muy informalmente, está interesada en clasificar los problemas en decidibles o no decidibles. Ella es la precursora de la teoría de la complejidad que nace en los años 1960 y es interesada en clasificar los problemas decidibles según su dificultad. Esta es una área de investigación muy activa, y su pregunta abierta central es decidir si \textsf{P}=\textsf{NP} o no.
Notas
La tercera área principal que constituye TC es la teoría de la complejidad. En este curso esta parte será tratada de manera un poco transversal.↩︎
Esto ha sido argumentado en el libro Mathematics and Computation by Avi Wigderson.↩︎