- 6.045: Automata, Comput, & Complexity
- Part One: Automata and Languages
- Part Two: Computability Theory
- Part Three: Complexity Theory
6.045: Automata, Comput, & Complexity
Provides an introduction to some of the central ideas of theoretical computer science, including circuits, finite automata, Turing machines and computability, efficient algorithms and reducibility, the P versus NP problem, NP-completeness, the power of randomness, cryptography, computational learning theory, and quantum computing. Examines the classes of problems that can and cannot be solved in various computational models.
- Introduction to the Theory of Computation
third edition by MICHAEL SIPSER
6.840:Theory of Computation
A more extensive and theoretical treatment of the material in 6.045J/18.400J, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. Students in Course 18 must register for the undergraduate version, 18.404.
Theory is relevant to practice. It provides conceptual tools that practitioners use in computer engineering. Designing a new programming language for a specialized application? What you learned about grammars in this course comes in handy. Dealing with string searching and pattern matching? Remember finite automata and regular expressions. Confronted with a problem that seems to require more computer time than you can afford? Think back to what you learned about NP-completeness. Various application areas, such as modern cryptographic protocols, rely on theoretical principles that you will learn here.
Theory also is relevant to you because it shows you a new, simpler, and more elegant side of computers, which we normally consider to be complicated machines. The best computer designs and applications are conceived with elegance in mind. A theoretical course can heighten your aesthetic sense and help you build more beautiful systems.
Finally, theory is good for you because studying it expands your mind. Computer technology changes quickly. Specific technical knowledge, though useful today, becomes outdated in just a few years. Consider instead the abilities to think, to express yourself clearly and precisely, to solve problems, and to know when you haven’t solved a problem. These abilities have lasting value. Studying theory trains you in these areas.
0.1 Automata, Computability, and Complexity
0.2 Mathematical Notions and Terminology
0.3 Definitions, Theorems, and Proofs
Seeing where you run into difficulty when you attempt to find a counterexample can help you understand why the statement is true.
0.4 Types of Proofs