This webpage is not longer current. See this for the current webpage of 6.045

Automata, Computability, and Complexity

Slower paced than 6.840J/18.404J. Introduces basic mathematical models of computation and the finite representation of infinite objects. Finite automata and regular languages. Context-free languages. Turing machines. Partial recursive functions. Church's Thesis. Undecidability. Reducibility and completeness. Time complexity and NP-completeness. Probabilistic computation. Interactive proof systems.

This course is offered Spring of 2004, from 11 to 12:30 (MW) in 37-212. Recitations will be held on Thursdays at 1pm in 34-304 and 4pm in 34-304. Office hours for the TA are Mondays 4-5pm in 32-G694 (actually somewhere near the TA's office in Stata Center, Gates Tower, Room 694) and by appointment.

Course Home Page
General Information/Policies
Contact Info
Objectives and Outcomes
Course Materials by Lecture Date

Last modified: Wednesday, March 31, 2004