Theory of Computation

Version 2026-2027 Q1
Last update: September 09, 2026
Credits & Copyright

This course offers an introduction to the theory of computation. It explores key topics such as formal models of languages, finite automata and regular languages, context-free languages, Turing machines and the theory of computability, and glimpses of computational complexity theory.

The main objective is to deepen the student’s understanding of computer science by introducing a philosophical perspective and engaging with fundamental questions like

What is computable and what is not?

and

Why are some computational problems easy, others difficult, and some impossible to solve?

The concepts and techniques presented are intentionally foundational, designed to remain relevant regardless of changes in hardware or software trends.