6.045J is a course in the department's "Theoretical Computer Science" concentration. This course has virtually all of its materials online, including a full set of homework assignments and exams.

This course introduces basic mathematical models of computation and the finite representation of infinite objects. 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.