La teoría de la computación se ocupa de determinar qué problemas pueden ser resueltos computacionalmente y con qué eficiencia. La teoría considera distintos modelos de cómputo, como los autómatas finitos (que son los más sencillos), las máquinas de Turing (que son las computadoras usuales de hoy en día) y las computadoras cuánticas (cuyo funcionamiento no es digital). Las lógicas y los lenguajes formales juegan un rol central en la teoría de la computación porque permiten expresar propiedades de los programas y razonar sobre su comportamiento. La teoría de la computación también se encarga de entender el límite entre los problemas computables y los no-computables y, dentro del mundo de lo computable, clasificarlos de acuerdo a su grado de simpleza o dificultad.

En particular, estudiamos lógicas con buen comportamiento computacional, como las lógicas modales, tanto desde el punto de vista de la teoría de modelos como desde el de la teoría de prueba. Analizamos lenguajes eficientes de consultas que permiten razonar sobre distintas estructuras de representación del conocimiento. A un nivel más abstracto, investigamos las propiedades teóricas de los sistemas de reescritura y los modelos de cómputo fuertes, como el cálculo lambda. A la inversa, estudiamos modelos de cómputo débiles, como los autómatas finitos y sus numerosas variantes. Nos ocupamos también de la noción de aleatoriedad en relación a los distintos modelos de cómputo y a los  grados de dificultad de los problemas. Por último, introducimos nociones provenientes de la teoría de funciones computables y de la teoría de la aleatoriedad en el procesamiento cuántico de la información y en algunos modelos computacionales que intentan explicar ciertas características de la cognición humana.

Keywords: Lógicas Modales, Complejidad, Cuántica