Università degli Studi di Udine
Facoltà di SS MM FF NN


Fondamenti dell'Informatica
Foundations of Computer Science: Mathematical theory of computation


Instructor: Prof. Simone Martini
Teaching assistant: Dr. Fabio Alessi
C.so di laurea: Informatica

Aims of the course

The course will study the fundamentals of the theory of computation. Main issue will be the limitations the notion of algorithm (effective procedure) imposes on the class of computable functions. While the first part of the course will study the main properties of such a class, the second part will present classes of functions computable with algorithms with limitations in space and/or time. We will further explore the relations of these classes with important classes of formal languages.

Program

  1. Computability theory
    Algorithms and effective procedures. Register machines (URM) and URM-computable functions. Recursive functions and their enumerability. Universal function. Equivalence of recursiveness and URM-computability. Turing machines. Church thesis. S-m-n- theorem. Recursive and recursively enumerable sets. Theorems of Rice and Rice-Shapiro. m-reducibility; m-degrees; arithmetic hierarchy. Productive and creative sets. Second recursion theorem, Myhill theorem. Recursive operators, Myhill-Shepherdson theorem, first recursion theorem.
  2. Complexity theory
    Turing machines with limited resources; relations with URMs. Complexity classes. Some important classes: P, NP, EXP, PSPACE. (Polynomial) reductions and complete problems. NP-completeness, Cook theorem; examples of NP-complete problems. Beyond NP: the polynomial hierarchy.
  3. Formal languages theory
    Formal languages and operations on languages. Grammars and Chomsky hierarchy. Regular languages, regular expressions, linear grammars. Finite automata: deterministic, non- deterministic, with epsilon moves; equivalences. Pumping lemma for regular languages and closure properties. Myhill-Nerode theorem. Decidable properties of regular languages. Context free languages: derivation trees, grammars, push-down automata. Chomsky and Greibach normal forms. Pumping lemma for context free languages and closure properties.

Textbooks: