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.
Prerequisite
1.
CS 310 or
MATH 300 or 2. Completion of a general education math reasoning core course.