
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
 Computability theory
Algorithms and effective procedures. Register machines (URM) and
URMcomputable functions. Recursive functions and their
enumerability. Universal function. Equivalence of recursiveness
and URMcomputability. Turing machines. Church thesis. Smn
theorem. Recursive and recursively enumerable sets. Theorems of
Rice and RiceShapiro. mreducibility; mdegrees; arithmetic
hierarchy. Productive and creative sets. Second recursion
theorem, Myhill theorem. Recursive operators, MyhillShepherdson
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. NPcompleteness,
Cook theorem; examples of NPcomplete problems. Beyond NP: the
polynomial hierarchy.
 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. MyhillNerode
theorem. Decidable properties of regular languages. Context free
languages: derivation trees, grammars, pushdown automata.
Chomsky and Greibach normal forms. Pumping lemma for context
free languages and closure properties.
Textbooks:
 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, AddisonWesley, Reading 1979.
 Part 3.
C. H. Papadimitriou, Computational Complexity, AddisonWesley, Reading
1994.