18.404/6.1200 (formerly 6.840) Fall 2022
Introduction to the Theory of Computation

Required background. To succeed in this class, you need experience and skill with mathematical concepts, theorems, and proofs. If you did reasonably well in 18.062, 18.200, or any other substantial, proof-oriented mathematics class, you should be fine. The class moves quickly, covering about 90% of the textbook. The homework assignments generally require proving some statement, and creativity in finding proofs will be necessary.

Textbook: Introduction to the Theory of Computation, 3rd edition, Sipser, published by Cengage, 2013. It has an errata web site. You may use the 2nd edition, but it is missing some additional practice problems. You may use the International Edition, but it numbers a few of the problems differently.

2020 Lectures