Theory of Computation (Fall 2022) studies models of computation, and the problems they can solve. We will begin by studying finite-state automata. This is a primitive model of computation consisting of a finite collection of states, and the computer moves from state to state depending on letters on a tape that the machine reads. There are several variants on finite-state automata, including deterministic finite-state automata, nondeterministic finite-state automata, 2-way finite state automata, and multi-track finite-state automata. But, as we shall see, these models are all equivalent to each other in terms of their computational power: they are all able to recognize exactly the so-called regular languages.
The next model we will look at is that of the a pushdown automaton. This is a more powerful model of computation, that has a memory in the form of a stack. They are able to recognize a wider class of languages: the so-called context-free languages.
Finally, we will look at the most powerful model of computation: the Turing machine. This model of computation is as powerful as any modern programming language. The main question here is not so much what a Turing machine can do, since it can do essentially everything, but how fast it can do it. We will look at the various complexity classes, including P, NP, PSPACE, EXPTIME, and so forth, including a discussion of the most famous problem in the field, namely the P vs. NP problem.
This class will meet September 26—December 7, with a break the week of November 21. Everyone will attend lectures online on Mondays from 6:30–8:30 PM Pacific time. Online students will attend problem sessions on Tuesdays from 5:00–7:00 PM Pacific time. In-person students will attend problem sessions on Wednesdays from 6:30–8:30 PM Pacific time.
Applications for this class are due July 24. Click here to apply!
Euler Circle 