MA488
 Introduction to Computability Theory
 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 Gdel's Incompleteness Theorem.   
Prerequisite: MA215, MA238.