Automata, Computability, and Complexity

The course provides an introduction to the theory of computation. The treatment is mathematical, but the point of view is that of Computer Science. Roughly speaking, the theory of computation consists of three overlapping subareas: (1) formal languages and automata; (2) computability and recursive function theory; (3) complexity theory. The course will focus mostly on (1) and (2). The topics covered include finite automata and regular languages, context-free languages, Turing machines, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness.