An introduction to the foundations of computer science. In this course, we will look at some of the classical models of computation, their formal capabilities, , the limits of computabiity and why it matters. We will also study complexity theory, which looks at the resource (space and time) demands for problems that can be computed.