Theory of Computation

Catalog description

This course covers basic theoretical principles embodied in formal languages, automata, computability, and computational complexity. Topics include finite automata, pushdown automata, non-determinism, regular expressions, context-free grammars, Turing machines, Gödel numbering, Church’s thesis, the halting problem, unsolvability, and computational complexity.