*Instructor: *Dr Gyula Y. KATONA

*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.