# Graduate Computer Science

# CS G714: Theory of Computation

Examines formal models of computation, notions of undecidability, and basic complexity theory. Models of computation include finite state automata, pushdown automata, and Turing machines. Discusses the properties of regular sets and context-free languages. Also covers partial recursive functions, primitive recursive functions, recursively enumerable sets, Turing decidability and unsolvable problems. Discusses the concept of reductions, time and space complexity classes, and the polynomial-time hierarchy.

**Prerequisites:**

CS G713 MS: Theory

**Credit hours:**4