Apr 13, 2021  
2019-2020 Undergraduate Catalog 
2019-2020 Undergraduate Catalog [Archived Catalog]

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: Previous or Concurrent Enrollment in MA 207 or MA 240.