6.5400J / 18.404/4041J Theory of Computation
Repeats every week every Tuesday and every Thursday until Tue Dec 09 2025 except Tue Nov 11 2025, Thu Nov 27 2025.
Thu, 09/04/2025 - 2:30pm to 4:00pmLocation:
54-100
Instructor:
Michael Sipser
A more extensive and theoretical treatment of the material in 6.1400J/18.400J, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. Students in Course 18 must register for the undergraduate version, 18.404.