# 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.


_Figure 001 — The Turing machine: a tape, a head, and a finite control.
_

_Figure 002 — A finite automaton reading its input, symbol by symbol.
_

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.


_Figure 003 — The tape: unbounded memory, one cell at a time.
_

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.


_Figure 004 — The ladder of languages — and a wall: HALT.
_

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.


_Figure 005 — A grammar parses a string into a tree.
_

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.


---

_Coming soon — notes for this subject are in progress._