Theory of Computation
Before asking how to compute something efficiently, theory asks whether it can be computed at all — and if so, how powerful a machine that requires.
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 hierarchy of increasing power. Each level fixes exactly which problems its model can and cannot solve — the foundation under every parser, regex, and compiler.
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 is the Church–Turing thesis: anything any reasonable machine can compute, a Turing machine can compute too. It is why one simple model defines computation itself.
Undecidability follows. Once a model is powerful enough to describe itself, there are questions about itself it cannot answer — 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 limits are saves the effort of trying.
Theory delimits what is possible. It replaces “I couldn’t get it to work” with a proof that it cannot work — or that it can.