### Free University of Bozen-Bolzano

Faculty of Computer Science

Master of Science in Computer Science

# Theory of Computing

# Final Program A.Y. 2014/2015

**Teaching material.**

**[M1]** *Introduction to Automata Theory, Languages, and
Computation (3rd edition).* J.E. Hopcroft, R. Motwani, J.D. Ullman.
Addison Wesley, 2007.

**[M2]** *Lecture Notes for Theory of
Computing*. Diego Calvanese. 2013. Available on the course
web page as scanned pages in pdf.

**[M3]** *Languages and Machines (3rd edition).* Thomas
A. Sudkamp. Addison Wesley, 2005.
Only Chapter 13.

**[M4]** *The
Convenience of Tilings.* Peter van Emde Boas. In *Complexity, Logic,
and Recursion Theory*, volume 187 of Lecture Notes in Pure and Applied
Mathematics, pages 331-363, 1997.

**Basic notions** [M1: Chapter 1]
- basic notions about functions, relations, mathematical logic,
formal languages
- formal proofs (deductive proofs, proofs by contradiction,
equivalences about sets, inductive proofs)

**Turing Machines** [M1: Chapter 8]
- The "basic" TM model
- extended TMs

**Decidability and undecidability** [M1: Chapter 9]
- recursive, recursively-enumerable, and non recursively enumerable
languages
- the diagonal and universal languages
- arithmetization of TMs

**Recursive functions** [M3]
- primitive recursive functions
- mu-recursive functions
- relationship between TMs and recursive functions

**P, NP, NP-completeness** [M1: Chapter 10]
- the classes P and NP
- reductions
- NP-completeness and NP-complete problems

**Polynomial Hierarchy and PSPACE** [M1: Chapter 11, M2]
- complements of languages in NP
- polynomial hierarchy
- the classes PSPACE and NPSPACE

**Logarithmic space**
- logspace reductions
- composition of function computations
- the classes L and NL

**Tiling problems**
- definition of tiling problems
- encoding Turing machine computations as tilings

course home page

*Last modified:
Friday, 16-Oct-2015 19:39:25 CEST
*