Theory of Computation

Catalog description

This course introduces a formal framework for investigating both the computability and complexity of problems. Theoretical foundations of computer science and formal models of computation are covered. Students study several models of computation including finite automata, regular expressions, formal languages, Chomsky language hierarchy, context-free grammars and Turing machines. Topics include undecidable problems, the halting problem and the P versus NP problem.