To introduce the Mathematical basis and practical implications of the classical theory of computability and to consider the extent to which this is still relevant to modern developments in computing.
INTENDED LEARNING OUTCOMES (ILOs) (see assessment section below for how ILOs will be assessed)
SYLLABUS PLAN - summary of the structure and academic content of the module
Formal Languages: Regular languages and regular expressions, context-free languages and grammars, pumping lemmas and other methods of proof. Automata: Finite-state automata, elimination of non-determinism, Kleene's theorem, push-down automata, Turing machines, the Universal Turing Machine. Computability: Recursive insolubility of the halting problem for Turing machines, the Church-Turing thesis and its variants, other models of computation the quest for hypercomputation. Complexity: Polynomial and exponential algorithms, the satisfiability problem and NP-completeness, the P vs NP problem.
