Description of the course
The purpose of the course is to study the limits of computation, providing the formal tools and fundamental knowledge to study problems, both tractable and intractable, by a computer. The course is structured in two parts.
In the first part we consider the theory of formal languages and automata, moving from the simplest machines with finite states towards the most powerful Turing Machines and modern computer systems. We explore the limitations of all these systems in the hypothesis of no bound in computing resources such as time or space or energy, hence exploring the nature of problems that admit an algorithmic solution.
The second part considers instead the hierarchy of problems that can be computed within a fixed bound of resources (time and space), the interrelationships among complexity classes, and the study of both NP-complete and provably intractable problems, constituting the theory of computational complexity. The emphasis will be on written problem sets containing challenging problems. The key techniques to be learned are those of simulation of one computational model by another, reduction of one problem to another, and methods for classifying problem complexity.
Grading Scale and Policies
The final grade is based on the percentage of all available points that you receive. A typical example of how percentages might translate into letter grades is A: 91-100, B: 71-90, C: 51-70, D:31-50, E:0-30. Without prior arrangement, missed exams and late homework assignments are not graded for credit. In justified circumstances extra time can be requested.
The program is the same for graduate and undergraduate students. Undergraduate students will be assessed using the same scale as graduate students, with the percentage multiplied by a factor of 1.2 for evaluation purposes. Dedicated additional hours will be allocated for clarifications specifically intended for undergraduate students.
Schedule in Spring 2026: Tue & Thu 5pm - 6:15pm
The course on Theory of Computation (ToC) at UA
01/20: Introduction to ToC: the main problems in computability and complexity.
Slides 0, Video.
01/22 (online): Cantor’s theorem, languages over an alphabet, and the Entscheidungsproblem (the decision problem).
Video HD, Video, Notes.
Part 1 (Problems and Computation)
Regular languages, deterministic finite state automata (FSA).
Video, Notes
Non-deterministic FSA. The theorems of Rabin-Scott. Regular expressions.
Video, Notes
Myhill-Nerode characterisation of regular languages. Pumping Lemma for regular languages. Examples of use.
Video, Notes
Examples of Pumping Lemma regular languages. Context free languages.
Video, Notes
Normal forms and Pumping Lemma context free languages. Examples and closure properties of CFL. (Homework 1)
Video, Notes
Examples. Push Down Automata.
Video1, Note1, Video2, Note2
Primitive recursive functions, Turing Machines and computable functions. Church-Turing Thesis. Universality of the Turing model of computation. s-m-n theorem, compilation and interpretation by Futamura's projections. Non solvable problems.
Video, Notes, and a Beautiful Video with the A. Turing's Proof.
Recursive and recursive enumerable (re) sets, Post Theorem. Kleene theorem of characterisation of re sets.
Recursion theorems and Rice Theorem.
Examples. (Homework 2 and MidTerm exam)
Part 2 (Reduction: Towards Complexity Theory)
Reduction and completeness.
Properties of functional reduction.
Creative and productive sets. The Computability Hierarchy.
Examples and exercises
Supplementary material on exercises. (TBA)
Gödel Incompleteness. Computational complexity. (Homework 3 & Backup 1)
Blum’s abstract theory of computational complexity. Properties of computational complexity.
The Speed-up theorem
P and NP: properties.
P, NP and co-NP.
Reductions and completeness: SAT and Cook's Theorem. (Homework 4 & Backup 2)
Examples, EXP and NEXP.
Time hierarchy, Ladner’s theorem and Space complexity.
Final Exam.