MA 208 - Theory of Computation

Primitive recursion and recursive functions; Turing machines; weaker computational models, including finite state machines and pushdown automata; regular expressions and Kleene’s theorem; nondeterminism; Halting Problem and Rice’s Theorem; NP completeness. Emphasis on conceptual overview of the role the topics play in computing.

Credits: 4

Prerequisites/Restrictions: MA 160 or above; (Previous or Concurrent Enrollment in MA 207 or MA 240 recommended)