This is a course in the mathematical theory of computation. It is intended to give a detailed understanding of the basic concepts of abstract machines, information flow, computability, and complexity. The emphasis will be on appreciating the significance of these ideas and the formal techniques used to establish their properties. Topics chosen for study include: models of computation, primitive recursive and partial recursive functions, the Church-Turing thesis, limits to computation (undecidablility), reducibility, Rice's theorem and the recursion theorem, Godel's theorem, productive and creative sets, and the intrinsic difficulty of computational problems (especially NP-completeness).
CSE 2001, CSE 3101, general fourth-year CSE prerequisites.