Università degli Studi di Udine
Facoltà di SS MM FF NN
Foundations of Computer
Science: Mathematical theory of computation
Prof. Simone Martini
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
- 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.
- 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
- 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.
- Part 1.
N.J. Cutland, Computability: An introduction to recursive function theory,
Cambridge Univ. Press, Cambridge 1980.
- Part 2.
J.E. Hopcroft e J.D. Ullman, Introduction to automata, languages and
computation, Addison-Wesley, Reading 1979.
- Part 3.
C. H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading