18.404 Theory of Computation
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.
18.404 will not be offered this semester. It will be available in the Fall semester, and will be 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 http://www.google.com/search?&q=MIT+%2B+18.404&btnG=Google+Search&inurl=https site or on the 18.404 Stellar site.
© Copyright 2015 Yasyf Mohamedali