The theory of computation is a specialty within computer science that focuses on the development of both logical and mathematical models, abstracting from concerns about hardware and memory limits.
This theory was derived from work in the fundamental areas of 20th century mathematics by figures such as Kurt Godel and Alan Turing. According to Richard L. Epstein and Walter A. Carnielli in their book, "Computability" (1989), the resulting theory treats computers as "methods for pushing symbols around."
Kozen begins the first lecture in "Theory of Computation" by laying out the two central concerns of the course. These are the study of "various computational models and programming constructs" and the classification of problems "in terms of their inherent complexity."
Historically, a good starting point for discussion of such points is a 1936 paper written by Turing called, "On Computable Numbers." In this paper Turing defined what he called a universal machine (now called a Turing machine in his honor).
A Turing machine involves a finite set of states and a semi-infinite tape. The machine reads input and (based on that input) imprints symbols on the separate cells of the tape. The tape is called "semi-infinite" because it is delimited on the left end but unlimited on the right.
As Kozen puts it, the Turing machine provides a "model for defining basic time and space complexity" with definitions that "reflect fairly accurately our expectations of real-life computation."
Kozen goes on to discuss Savitch's theorem, named for Walter Savitch, a long-time professor at the University of California, San Diego. Savitch's theorem demonstrates that there is an algorithm for determining whether there is a path between two vertices in a directed graph.
Kozen notes that this has a bearing upon, although it is not identical to, "the most important open question in theoretical computer science" (the P = NP problem).
For example, if you define "P" as the set of all problems that can be easily solved, and "NP" as the set of all problems that are difficult to solve but can be easily recognized as accurately solved once somebody else has done so, then it seems intuitively obvious that "P" and "NP" are not the same set. If they were the same set, it would be a troubling fact for computer scientists, because it would mean that everything is (in principle) hackable.
However, neither Savitch's nor Kozen's theorems resolve the issue.
Kozen is also the author of "The Design and Analysis of Algorithms," which is a book that covers similar subject matter for graduate students already "familiar with the classical material normally taught in upper-level undergraduate courses" in the area.