Instructor: Dr Katalin FRIEDL

Text:  Michael Sipser:  Introduction to the Theory of Computation, Springer

Prerequisite: some introductory combinatorics, algebra  and number theory (e.g. definitions  and  basic properties of graphs,  binomial coefficients,  primes  and groups) is  helpful.

Course description:

• Finite automata, regular and non-regular languages, pumping lemma.
• Context-Free languages.
• Turing Machines, universal Turing machines.
• The existence of universal Turing machines.
• Recursive functions. Recursive, recursively enumerable languages.
• Algorithmic decidability,
•  Halting problem and other undecidable problems.
• Storage and time,  general theorems on space and time complexity
• Non-deterministic Turing-machines.  NP and co-NP.
• Cook's theorem: SAT is NP-complete.
• Other NP-complete problems.
• RAM machines.
• Kolmogorov-complexity of sequences.
• Communication complexity.