6 parts · 7 chapters
Theory of Computation
What computers can and cannot do, and what they cannot do quickly. This theory shows up as everyday bugs: a regular expression that hangs a server, a parser that cannot handle nesting, a static analyser that must give up, and a scheduling feature that turns out to be NP-hard. Measured in Node 25: the regex /^(a+)+$/ took 440 ms on a 27-character input and doubles with each extra character.
Six parts: finite automata and regular languages (with ReDoS measured); grammars and parsing; Turing machines; decidability and the halting problem; P, NP and reductions; and living with hard problems through approximation, heuristics and solvers.
automataDFAs, NFAs and regular expressions are the same power.
grammarsContext-free grammars handle nesting regexes cannot.
machinesTuring machines define what is computable at all.
limitsThe halting problem and Rice's theorem: what tools cannot decide.
complexityP, NP, NP-completeness and reductions.
practiceHeuristics, approximations and SAT/ILP solvers.
00
Automata and Regular Languages
Finite automata · ReDoS, measured
2 ch · ~12 min01Grammars and Parsing
A grammar and its parser
1 ch · ~8 min02Turing Machines
A machine that adds one
1 ch · ~8 min03Decidability and the Halting Problem
The proof, and what it means for tools
1 ch · ~8 min04P, NP and Reductions
Recognising hard problems
1 ch · ~8 min05Living with Hard Problems
A solver in twenty lines
1 ch · ~8 minFor programmers without a CS degreeUses Discrete Maths for sets, logic and proof; feeds Compilers and Algorithms.