CS 334 Theory of Computation
Introduction to models of computation and their languages: finite-state machines, non-determinism, and regular languages, pushdown automata and context-free languages, and Turing Machines and recursively enumerable languages. The limits of computability: The Church-Turing thesis, decidable languages, reducibility, the halting problem, and the recursion theorem. Time and space complexity measures, intractable problems, and the P vs. NP question.