Theory of Computation
Before we ask how to compute something efficiently, theory asks a deeper question: can it be computed at all — and if so, how powerful a machine do you need?
Start small. A finite automaton has no memory beyond its current state, yet it already captures every regular language — the patterns a regex can match, the tokens a lexer can split.
Finite automata, grammars, and Turing machines form a ladder of power. Climbing it tells you exactly which problems each model can and cannot solve — the foundation under every parser, regex, and compiler you’ll ever use.
Add a stack and you get a pushdown automaton — enough to parse balanced brackets and the grammars behind real languages. Add an unbounded tape and you get a Turing machine: the most powerful model we have, and, we believe, the most powerful there is.
That belief has a name — the Church–Turing thesis. Anything any reasonable machine can compute, a Turing machine can compute too; it is why one simple model gets to define computation itself.
Undecidability is the punchline. Once a model is powerful enough to describe itself, it can ask questions about itself that it cannot answer — and the halting problem is the first and sharpest of them.
It also draws hard limits. Some problems — like deciding whether an arbitrary program halts — are provably unsolvable by any computer, ever. Knowing where those walls are saves you from running head-first into them.
Theory is the map of what’s possible. It turns “I couldn’t get it to work” into “this cannot work, and here’s the proof” — or “this can, and here’s why.”