18.404 Theory of Computation


Class Info

A more extensive and theoretical treatment of the material in 6.045J/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.

This class has 6.042, and 18.200 as prerequisites.

18.404 will be offered this semester (Fall 2018). It is instructed by M. Sipser.

Lecture occurs 2:30 PM to 4:00 PM on Tuesdays and Thursdays in 2-190.

This class counts for a total of 12 credits.

You can find more information at the MIT + 18.404 - Google Search site.

Required Textbooks
Save up to up to 95% by purchasing through MIT Textbooks!
MIT 18.404 Theory of Computation Related Textbooks
MIT 18.404 Theory of Computation On The Web

© Copyright 2015