MATH 400 Foundations of Computability
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.
Prerequisite
Take the following:,1.
CS 310,
MATH 300 or PHIL 306,2. Completion of a general education math reasoning core,course.