This course is an introduction to the theory of computation, teaching: • How to reason precisely about computation and prove mathematical theorems about its capabilities and limitations. • Models of computation. These range from weak but useful models (such as finite-state machines) to universal models (such as Turing machines) that capture our intuitive notion of computation and allow us to reason about the capabilities of computers in a technology-independent manner. • The intrinsic limits of computation. Computational problems that cannot be solved by any algorithm whatsoever (undecidability), and problems that are solvable but require inordinate computational resources (computational complexity). • Formal language theory. The basics of grammars and parsing.