6.5400J / 18.404 / 4041J Theory of Computation
Repeats every week every Tuesday and every Thursday until Tue Dec 10 2024 except Tue Oct 15 2024, Thu Nov 28 2024.
Thu, 09/05/2024 - 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.