Università Roma Tre

The course Theory of Computation and Interaction provides a in-deep view of theoretical aspects related to the concept of computation and the study of relations between different models of computation. The basic knowledge on information technology is here extended with new concepts and theoretical viewpoints. The course is divided into two units of 6 CFU. At choice, the student can decide to pass the first unit or both (12 CFU). More specifically, the course provides a formal presentation of the concepts of algorithm and computability. After the introduction of the classical concept of computability as formalized by Alan M. Turing, we address the basic concepts of algorithmic complexity and problem decidability, functional models and functional programming. In the second unit, we focus on interactive paradigms in the theory of computation which allow the description of additional complexity classes and their use in the semantics of programming languages.