6.045/18.400 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 2002, from 11 to 12:30 (MW) in 24-121. Recitations times are 1 and 4, Thursdays, in 34-304. Office hours for the TA are 4:30 to 6, Tuesdays, in NE43-336, and by appointment.

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

Last modified: Wed Feb 27 16:48:24 EST 2002