Each of the seven modules below corresponds to a cluster of lectures from Michael Sipser's MIT 18.404J course. Inside every module you will find: a short narrative that builds the intuition; one or more interactive widgets (machine simulators, proof walkthroughs, reduction builders); and a set of practice problems taken from Introduction to the Theory of Computation (Sipser, 3rd ed.), each with hints and staged solutions.
The modules are designed to be read in order — later modules assume the language of earlier ones — but you can jump in anywhere if you already know the prerequisite vocabulary.
The course's five learning outcomes line up cleanly with the modules:
| CLO | Statement | Primary modules |
|---|---|---|
| CLO-1 | Use diagonalization to prove undecidability | Module 2, Module 7 |
| CLO-2 | Use informal and formal reductions to establish algorithmic unsolvability | Module 2, Module 3 |
| CLO-3 | Distinguish the complexity of finding vs verifying a solution | Module 4, Module 5 |
| CLO-4 | Use mapping reductions to establish hardness of computational problems | Module 5, Module 6 |
| CLO-5 | Use hierarchy theorems to establish separation between complexity classes | Module 7 |
Every module ends with a row of Sipser exercises you should now be able to solve. By the end of Module 7 you will be ready for the Sipser problems in chapters 4 through 9.
The whole course is, in the end, about drawing the following picture and knowing where each landmark lives:
Every solid boundary on this map is either a theorem we will prove together (P ⊆ NP ⊆ PSPACE ⊆ Decidable ⊊ RE) or an open question (P =? NP, NP =? PSPACE). By Module 7 you'll know which is which, and how the few known separations are forced by diagonalization.
Every interactive widget is hand-built; there is no math library running underneath. That is on purpose: the point is to see the algorithm execute, not to take its output on faith. If the diagonalization tableau looks like cheating, you can step through the construction one cell at a time and convince yourself it isn't.
The site is self-contained — no internet connection or login required. You can use it on a laptop in class, on a tablet at home, or projected on a board.