6.840[J] 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. Students in Course 18 must register for the undergraduate version, 18.404.

This class has 18.200, and 18.062J as prerequisites.

6.840[J] will be offered this semester (Fall 2017). 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. This is a graduate-level class.

You can find more information at the http://www.google.com/search?&q=MIT+%2B+sipser&btnG=Google+Search&inurl=https site.

MIT 6.840[J] Theory of Computation Related Textbooks

© Copyright 2015