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 half-credit in Mathematics at the 300 level. |