Grounds the cadet in the essentials of theory of computation: formal languages, automata, and computability theory. Frames computation in the context of the Chomsky hierarchy, the polynomial and exponential time hierarchies, and the decidability hierarchy. Explores fundamental limits on computation: what problems can never be solved, what problems can be solved but are intractable, and the class NP of problems that are thought to be intractable, but for which no proof of intractability exists to date.
