π Theory of Computation
Based on Maheshwari & Smid, "Introduction to Theory of Computation", licensed CC BY-SA 4.0.
What can be computed, how fast, and how do we prove it? Finite automata to NP-completeness, translated into runnable code and diagrams.
| Chapter | |||
|---|---|---|---|
| 1. | Finite Automata | Five components define a machine that reads input and accepts or rejects | π |
| 2. | Nondeterminism | Multiple paths at once, epsilon jumps, and the subset construction that removes them | π |
| 3. | Regular Expressions | A pattern language exactly as powerful as finite automata, plus a pumping lemma to prove limits | π |
| 4. | Context-Free Grammars | Production rules, parse trees, and the grammars behind every programming language | π |
| 5. | Pushdown Automata | A finite automaton with a stack, exactly as powerful as context-free grammars | π |
| 6. | Turing Machines | An infinite tape, a head, and states: the simplest model of general computation | π |
| 7. | Decidability | Some problems have no algorithm: the halting problem and diagonalization | π |
| 8. | Complexity | P, NP, and the million-dollar question of whether brute force can always be beaten | π |
πΊ Video lectures: MIT 6.045J Automata, Computability, and Complexity
Neighbors
- π Logic β GΓΆdel's incompleteness theorems are the theoretical ceiling
- β Algorithms β NP-completeness connects complexity to algorithm design
- π’ Discrete Math β formal grammars use combinatorial objects
- π Cryptography β computational hardness assumptions underlie modern crypto