Automata & Formal Languages · Instrument 05 · Hierarchy & Limits

Where computation runs out

Each machine in this series is strictly stronger than the last — and we can prove the gaps are real. The pumping lemma shows finite memory can't count; the Chomsky hierarchy stacks the classes; and diagonalization reveals problems no machine can ever solve. The ladder has a top, and even the top has a ceiling.

Pumping lemma
Chomsky hierarchy
Halting problem
The map
Pump a string
member (×3)6
pump count i1
A DFA with p states, reading a string of length ≥ p, must revisit a state (pigeonhole). The loop between visits is y — repeat it any number of times and the machine still ends in the same state. If a language has no such pumpable loop, it isn't regular.
pumping
Click a language
Each ring strictly contains the one inside it. A language's class is the weakest machine that can recognize it — and the pumping-style arguments prove the containments are proper: there's always a language in the gap.
the Chomsky hierarchy
Diagonalization
List every machine and run each on its own description. Define D to do the opposite of the diagonal: D halts on ⟨Mₖ⟩ exactly when Mₖ loops on ⟨Mₖ⟩. D disagrees with every machine somewhere — so D is on no row. Yet a halting-decider would let us build D. Contradiction.
no machine decides halting
The whole ladder
From a finite set of states to an unbounded tape — and then past the edge of what any machine can decide. Five rungs, one map.
class ↔ machine ↔ grammar ↔ limits