Find a concept
BRANCH OVERVIEW
Theory of computation
Languages, machines, and the limits of computation.
← All branches · Each sheet includes definitions, theorems, applications, and exercises with hints and worked solutions.
Theory of computation
Languages, machines, and the limits of computation.
- Finite automata & regular languagesFinite memory recognizes patterns whose relevant history has only finitely many cases.
- Context-free grammars & parsingA stack adds unbounded nesting to finite-state control.
- Turing machines, deciders & recognizersDistinguish computing an answer eventually from guaranteeing an answer on every input.
- Reductions & undecidabilityTransfer impossibility by showing how a hypothetical solver would solve a known impossible problem.
- P, NP & completenessAsk what can be computed efficiently after establishing that it can be computed at all.