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