​Finite Automata and Regular Languages, Properties of Finite Automata, Regular Expressions, The Pumping Lemma and Closure Properties; Universal Models of Computation, Encoding Instances, Choosing a Model of Computation, Model Independence, Turing Machines as Enumerators and Acceptors; Computability Theory, Primitive Recursive Functions, Partial Recursive Functions, Arithmetization: Encoding a Turing Machine, Programming Systems, Recursive and R.E. Sets, Rice's Theorem and the Recursion Theorem, Degrees of Unsolvability; Complexity Theory, Reductions, Classes of Complexity, Complete Problems; Some Important NP-Complete Problems, The Complexity of Approximation, Models of Parallel Computation, Communication and Complexity, Interactive Proofs and Probabilistic Proof Checking