MATH 400 Foundations of Computability
(3-0-3) This course is an introduction to fundamental questions of computer science, mathematics and philosophy of mathematics. In particular, it is an analysis of the capabilities and limitations of computability, logic and mathematical proof. Topics include finite automata and regular languages, pushdown automata and context-free languages, the Church-Turing thesis, decidability and the Halting Problem, Gödel's Incompleteness Theorems, the Axiom of Choice and some variants and an introduction to complexity classes and NP-completeness.