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)