Foundational course in the theory of computation, covering what is possible with different types of computational resources. Topics include automata, Turing machines, nondeterminism, reductions, decidability and undecidability, the limits of time and space resources, and complexity class hierarchies.