Is a given problem solvable by computers? If so, how much time (or memory) do we need to solve it? Can a solution be obtained in a practically feasible manner? Is your desktop computer more powerful than your wristwatch? These are fundamental questions in computer science, and this course attempts to answer (some of) them in a mathematical manner, i.e., with a pencil and a piece of paper. Why? Because such results are beautiful and ingenious. Besides, they so apply in practice more generally than any experiment.
Roughly, we shall talk about the following topics during this course:
| Introduction, rules of the game, mathematical preliminaries | 2 weeks |
| Finite automata and regular expressions | 2 weeks |
| Context-free languages | 2 weeks |
| Turing machines | 2 weeks |
| Undecidability | 2 weeks |
| Complexity | 3 weeks |