CS 614 Theory of Computation

Reviews the theory of the power and limitations of computation and computers: Turing machines, recursive and recursively enumerable functions, equivalence of computing paradigms (Church-Turing thesis), undecidability, intractability, and introduction to NP-completeness.