Course Description

MA488 Computability and Logic 0.5

Turing machines and concept of computability; automata; recursive functions; recursive and recursively enumerable sets; Church's Thesis; the halting problem and other unsolvable problems; NP-completeness; undecidability and Gödel's Incompleteness Theorem.††

Prerequisite: MA215, MA238 and a 0.5 MA credit at the 300 level.

DRAFT electronic version updated at 1:45 p.m. January 30, 2003

M. Watson, Editor Course Timetable