Computability and Logic CMPT 401 (3)

Explores the nature and limitations of computation and logic, and how they are connected. Topics include: Computable functions, Church's thesis, computationally unsolvable problems, recursively enumerable sets; Predicate calculus, including the completeness, compactness, and Lowenheim-Skolem theorems; Formal theories and the Gödel Incompleteness Theorem. Prerequisite: One of CMPT 307, PHIL 310, MACM 201; or a minimum of six upper division units in MATH. Students with credit for CMPT 409 under the title "Computability and Logic" may not take this course for further credit.