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)
02/06: Normal forms and Pumping Lemma context free languages.
02/11: Exercises and closure properties of CFL.
02/13: Exercises and Push Down Automata.
TBA: Supplementary material on the relation between Turing Machines and Gödel-Kleene partial Recursive Functions.
02/18: Turing Machines and computable functions. Church-Turing Thesis. Universality of the Turing model of computation.
02/20: s-m-n theorem, compilation and interpretation by Futamura's projections. Non solvable problems.(Homework 2)
Beautiful Video with the Proof
02/25: Recursive and recursive enumerable (re) sets, Post Theorem.
02/27: Kleene theorem of characterisation of re sets. Examples.
03/04: Recursion theorems.
03/06 Rice Theorem and examples. Exercises.
03/18: Reduction and completeness (Mid Term exam)
Part 2 (Reduction: Towards Complexity Theory)
03/20: Properties of functional reduction.
03/25: Creative and productive sets. The Computability Hierarchy.
TBA: Supplementary material on Gödel Incompleteness.
03/27: Examples
04/01: Examples and exercises (Homework 3)
04/03: Computational complexity and Blum’s abstract theory of computational complexity.
04/08: Properties of computational complexity.
04/10: The Speed-up theorem
04/15: P and NP: properties.
04/17: Reductions and completeness. NP-completeness.
04/22: Examples: SAT and Cook's Theorem.
04/24: Examples.
04/29: Examples, EXP and NEXP. (Homework 4)
05/01: Time hierarchy, Gap Theorem and Ladner’s theorem.
05/06: Space hierarchy, final remarks.
TBA: Final Exam.