Theory of Computation
Last update: 2026-02-10
Version 2025-2026 Q2
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—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.
The course includes significant mathematical content. Students are expected to have prior experience with writing mathematical proofs and a general level of mathematical maturity. For those who meet these criteria and are curious about the theoretical limits of computation, the course promises to be both intellectually stimulating and enjoyable.