*Instructor: *Dr Gyula Y. KATONA

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

*Prerequisite*:
Prerequisite: some introductory combinatorics (e.g. definitions
and basic properties of graphs, binomial coefficients, primes) is
helpful, but not absolutely necessary.

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