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 2007, from 11 to 12:30 (MW) in 32-144. Recitation times are Thursdays, 12-1pm and 1-2pm in 26-328. Office hours for the TA are on Fridays at 12-1pm, and Mondays 12:30-1:30pm in the neighborhood of 32-G614.


You can check your grades here . You need MIT certificates in order to access the site. If you are not in the database, please follow the link to add yourself to the class list.

Evaluation Forms:

Please fill up the HKN course evaluation form here . The deadline is May 20th . Thanks!
Course Home Page
General Information/Policies
Contact Info
Objectives and Outcomes
Course Materials by Lecture Date

Last modified: Monday, May 7th, 2007