A survey of formal models and results that form the theoretical foundations of computer science; typical topics include finite automata, Turing machines, undecidable problems, context free languages and computational complexity.
- Formal definitions of computation, languages and computability
- Models of Computation: finite state automata, pushdown automata, grammars and Turing machines; deterministic and non-deterministic machines
- The Halting Problem, reductions, and NP-completeness
- Dealing with intractability (if time permits)