Course Description

In this course, we study the principal concepts of calculability and algorithmic complexity. After having introduced Turing machines as a principal model of calculation - as well as the properties of these machines (universality, non-determinisme, k-band machines, and Church-Turing thesis) – we study the existing non calculable functions (and undecidable problems). This will emphasize the power classical models and their efficiency due to reduced calculations. We also introduce the notion of complexity measurement (space and time) and the classes of distinct complexities (P, PSPACE, NP, EXPTIME, …).