Theory of Computation & Complexity
What can be computed, and how hard it is.
Finite Automata & Regular Languages
Finite automata are the simplest machines that can recognize patterns — and their limits reveal the deepest truths about what computation itself can and cannot do.
Regular Expressions & the Pumping Lemma
Regular expressions and finite automata are two faces of the same coin — the pumping lemma is the scalpel that cuts away everything they cannot describe.
Context-Free Grammars & Pushdown Automata
Context-free grammars and pushdown automata reveal the recursive heart of programming languages — where finite memory meets infinite structure.
Turing Machines & the Church-Turing Thesis
Turing machines define what computation IS — and their most beautiful theorem is a proof that some things can never be computed, by any machine, ever.
Decidability & the Halting Problem
Some problems are mathematically impossible to solve — not hard, not slow, but provably unsolvable by any program that could ever exist.
Reducibility & Undecidability
Reducibility is the universal key that unlocks undecidability: once you know one problem is unsolvable, you can prove infinitely many others are too — and Rice's Theorem shows the entire landscape of program-behavior questions is permanently out of reach.
Time Complexity: P and NP
P vs NP is the deepest unsolved question in computer science: can every problem whose solution is easy to check also be solved efficiently?
NP-Completeness in Depth
NP-completeness reveals the deepest mystery in all of computer science: why some problems seem to resist every clever algorithm ever invented — and why thousands of them all share the same fate.
Space Complexity & Beyond
Space complexity reveals that asking "how much memory does a computation need?" leads to a rich hierarchy rivaling time complexity — and sometimes collapses it in surprising ways.