Theory of Computation
MIT's course on computability and computational complexity theory covers regular and context-free languages, decidable and undecidable problems, reducibility, and recursive function theory. It moves into time and space measures of computation, completeness, hierarchy theorems, and the study of inherently complex problems, then extends into oracles, probabilistic computation, and interactive proof systems. Materials come from MIT OpenCourseWare and include lecture notes, problem sets, and exams used in the actual MIT class, letting learners work through the same assignments assigned to MIT students. The course is aimed at those with a background in discrete mathematics and algorithms who want a rigorous grounding in what can and cannot be computed, and how efficiently. No certificate is offered, but all materials are free to access under MIT's OpenCourseWare license.