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 G”del's Incompleteness Theorem. Prerequisite: MA215, MA238.