The theory of computation asks what can be computed at all, independent of hardware or language — and answers with a hierarchy of machine models, each with problems it can and provably cannot solve. The punchline of the course is negative and permanent: some precisely-stated problems are undecidable, and no future technology changes that.
Each machine model recognizes a class of formal languages, and each strictly contains the last:
| Level | Grammar | Machine | Canonical language | Can't do |
|---|---|---|---|---|
| 3 | Regular | Finite automaton (DFA/NFA) | (ab)^* | Counting: a^n b^n |
| 2 | Context-free | Pushdown automaton (stack) | a^n b^n, balanced parens | Cross-matching: a^n b^n c^n |
| 1 | Context-sensitive | Linear-bounded automaton | a^n b^n c^n | — |
| 0 | Unrestricted | Turing machine | Anything computable | The undecidable |
The engineering shadow of this table: regular languages are lexers and regex engines; context-free grammars are parsers and every programming language's syntax (the stack is exactly what nested structure needs — see Compiler Design Basics); and the pumping lemmas for regular and context-free languages are the tools that prove a task needs a stronger machine — the formal reason you cannot parse HTML with a regex.
A CFG is productions like S \to aSb \mid \varepsilon (generating a^n b^n). Derivations form parse trees; a grammar is ambiguous when some string has two parse trees — the dangling-else problem is the classic instance, resolved in real languages by grammar refactoring or precedence declarations. Deterministic CFLs (parseable by LL/LR machinery with no backtracking) are the practically relevant subclass: they are why parser generators exist and why language designers avoid ambiguity.
A Turing machine — finite control plus an unbounded tape — is the maximal model: everything proposed since (lambda calculus, RAM machines, your laptop, quantum computers for computability purposes) computes exactly the same class of functions. That empirical convergence is the Church-Turing thesis. Two refinements matter constantly: a decider always halts with yes/no; a recognizer halts on yes-instances but may loop forever on no-instances — the difference between decidable and merely recognizable (semi-decidable) languages. The universal Turing machine — one machine that simulates any other from its description — is the theoretical seed of the stored-program computer and of interpreters.
Theorem (Turing, 1936): no program H(P, x) can correctly decide, for every program P and input x, whether P halts on x.
The proof is a diagonal trap in four lines: suppose H exists; build D(P) = "if H says P halts on input P, loop forever; else halt." Now ask what D(D) does — either answer contradicts H's verdict on it. So H cannot exist. The structure is the same self-reference engine as Cantor's diagonal and Gödel's incompleteness — one idea, three monuments.
Undecidability spreads by reduction: if a decider for problem B would let you build one for the halting problem, then B is undecidable too. This is the standard proof pattern (note the direction — reduce from the known-hard problem to the new one). The wholesale version is Rice's theorem: every non-trivial property of a program's behavior (its input/output semantics) is undecidable — does it ever print a secret, does it equal this other program, is it a virus. This is the theorem that stands behind every static-analysis disclaimer: perfect behavioral analysis of arbitrary code is impossible, so real tools approximate — sound-but-incomplete or complete-but-unsound, never both. Termination provers, verifiers, and malware detectors all live inside this boundary, succeeding on restricted patterns precisely because the general problem is closed.
Computability sorts problems into possible and impossible; complexity theory sorts the possible by cost — P, NP, and the hardness machinery are the next course, covered in NP-Complete and NP-Hard Computability. The reduction technique carries over intact, with resource bounds attached.