Search Results

18.404 Theory of Computation

Prereq: 18.200 or 18.062[J]
U (Fall)
12 Units

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

M. Sipser

See more...

Subject meets with 6.840[J], 18.4041[J]

Department of Mathematics

The Department of Mathematics offers training at the undergraduate, graduate, and postgraduate levels. Its expertise covers a broad spectrum of fields ranging from the traditional areas of "pure" mathematics, such as analysis, algebra, geometry, and topology, to applied mathematics areas such as combinatorics, computational biology, fluid dynamics, theoretical computer science, and theoretical physics.