This course features a full set of homework
assignments. In addition, the
recitation section includes many practice problems. 6.045J is a course in the department's "Theoretical Computer Science" concentration.
» View an older version of this course en Español or em Portugues courtesy of Universia. Please note that since our Spring 2005 publication, the translated version available from Universia may not have the most current content that is available on the MIT OCW site.
This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. The course is slower paced than
6.840J/18.404J. Topics covered include: 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, and interactive proof systems.