Automata, Computability, and Complexity
MIT OpenCourseWare's introduction to theoretical computer science, covering finite automata, circuits and decision trees, Turing machines, computability, and reducibility. The course builds toward the P versus NP problem and NP-completeness, then examines randomness, cryptography and one-way functions, computational learning theory, and quantum computing. Materials include lecture notes, problem sets, and exams covering which problems different computational models can and cannot solve, and why. The course frames these topics historically, starting from ancient ideas about mechanical computation before moving into the twentieth century models that define the field. As with other MIT OpenCourseWare offerings, materials are free to access under a Creative Commons license, with no certificate offered. It suits learners with some mathematical maturity looking for a rigorous grounding in what computers can and cannot compute.