Mar 28, 2024  
2014-2015 Undergraduate Catalog 
    
2014-2015 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.

Prerequisites: MA 207 or MA 240

Full course