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 exceptional 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 2025: Tue & Thu 12:30pm - 1:45pm
The course on Theory of Computation (ToC) at UA
01/21: Introduction to ToC: the main problems in computability and complexity.
Slides 0
01/23: Cantor’s theorem, languages over an alphabet, and the Entscheidungsproblem (the decision problem).
Video HD, Video, Notes, Zoom.
Part 1 (Problems and Computation)
01/28: Regular languages, deterministic finite state automata and non-deterministic ones. The theorems of Rabin-Scott.
Video, Notes
01/30: Myhill-Nerode characterisation of regular languages.
Video, Notes
02/04: Pumping Lemma for regular languages. Examples of use. Context free languages. (Homework 1)
Video, Notes
02/06: Normal forms and Pumping Lemma context free languages.
Video, Notes
02/11: Exercises and closure properties of CFL.
Video, Notes
02/13: Exercises.
Video, Notes
02/18: Push Down Automata
Video, Notes
02/20: Primitive recursive functions, Turing Machines and computable functions. Church-Turing Thesis. Universality of the Turing model of computation.
Video, Notes
02/25: s-m-n theorem, compilation and interpretation by Futamura's projections. Non solvable problems.(Homework 2)
Video, Notes and a Beautiful Video with the Proof.
02/27: Recursive and recursive enumerable (re) sets, Post Theorem. Kleene theorem of characterisation of re sets.
Video, Notes
03/04: Recursion theorems and Rice Theorem.
Video, Notes
03/06: Rice Theorem: Examples
Video, Notes
Part 2 (Reduction: Towards Complexity Theory)
03/18: Reduction and completeness (Mid Term exam)
Video, Notes
03/20: Properties of functional reduction.
Video, Notes
03/25: Creative and productive sets. The Computability Hierarchy.
Video, Notes
03/27: Examples
Video, Notes
04/01: Examples and exercises
Video, Notes
04/02: Supplementary material on exercises. (GS701 at 10am-11:30am)
Video, Notes
04/03: Gödel Incompleteness. Computational complexity.
Video, Notes
04/08: Blum’s abstract theory of computational complexity. Properties of computational complexity. (Homework 3 & Backup 1)
Video, Notes
04/10: The Speed-up theorem
Video, Notes
04/15: P and NP: properties.
Video, Notes
04/17: P, NP and co-NP.
Video, Notes
04/22: Reductions and completeness: SAT and Cook's Theorem.
Video, Notes
04/24: Examples.
Video, Notes
04/29: Examples, EXP and NEXP. (Homework 4 & Backup 2)
Video, Notes
05/01: Time hierarchy, Ladner’s theorem and Space complexity.
Video, Notes
05/14: Final Exam!!