MIT OpenCourseWare

Browse materialsMIT 6.045J · Spring 2011

Automata, Computability, and Complexity

Subject: Mathematics

Art: Palmer, Edward, 1803-1872, Figures 113-123. Plate Electrical Machines, 1840 · Public domain

Instructor: Prof. Scott Aaronson
Term: Spring 2011
Level: Undergraduate
What's inside: 1 lecture note · 30 other files · 3 web pages
Materials open: MIT OCW

Start here

Start course: Lecture 1: Introduction Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 6.045J Automata, Computability, and Complexity, Spring 2011, Prof. Scott Aaronson — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: MIT's own listing order, section by section. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.

Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.

Before you start

Prerequisites are not listed here. Check MIT's own syllabus for this course.

This course’s cited books, in our reading lists: Introduction to the Theory of Computation · Computational Complexity: A Modern Approach

How this course was organized

What's here, and what isn't

A lecture sequence of 23 items is confirmed. Assignment and exam materials exist too, but MIT's own order for them could not be verified, so they're shown as materials below rather than a sequence.

Not included here

2 items from the source could not be safely included:

MIT's page format for this item wasn't recognized clearly enough to place it safely.
Referenced in a table, but without MIT's own verified order, so it isn't used to claim a sequence.

Materials by section

Grouped by section, as MIT organized them. Not sequenced or ordered.

Lecture Notes

24 files

Assignments

MIT OpenCourseWare, Prof. Scott Aaronson, 6.045J Automata, Computability, and Complexity, Spring 2011.

License: CC BY-NC-SA 4.0 · Edition: Spring 2011 · Open the original course on OCW ↗

Organized by RedLectern, independent of MIT and not endorsed by MIT.

Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.

Automata, Computability, and Complexity

Before you start

What's here, and what isn't

Not included here

Materials by section

Lecture Notes

Assignments

Lecture 1: Introduction

Lecture 2: Logic, circuits, and gates

Lecture 3: Deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs)

Lecture 4: NFAs and regular expressions

Lecture 5: Non-regular languages and the pumping lemma

Lecture 6: Turing machines

Lecture 7: Decidability

Lecture 8: Undecidable problems and Post correspondence problem (PCP)

Lecture 9: Mapping reducibility and Rice’s theorem

Lecture 10: Self-reference and the recursion theorem

Lecture 11: Introduction to cryptography

Lecture 12: Complexity theory

Lecture 13: Pseudorandom generators and one-way functions

Lecture 14: Public-key cryptography

Lecture 15: More complexity theory

Lecture 16: More NP-completeness

Lecture 17: Probabilistic Turing machines and complexity classes

Lecture 18: Trapdoor one-way functions and zero-knowledge proofs

Lecture 19: Probably approximately correct (PAC) learning

Lecture 20: More PAC learning

Lecture 21: Introduction to quantum

Lecture 22: Quantum mechanics and BQP

Lecture 23: Quantum algorithms