Models of Computation: 20172018
Lecturer 

Degrees 
Part A — Computer Science and Philosophy 
Term 
Michaelmas Term 2017 (16 lectures) 
Overview
This course introduces the classical mathematical models used to analyse computation, including finite state automata, grammars, and Turing Machines.A computer scientist should be able to distinguish between what can be computed and what cannot. This distinction can only be made with a good scientific model of computers and computation. This course introduces the powerful idea of using a mathematical model to analyse computation.
This course describes a number of different models of computation which were proposed and analysed over the past century. Many of these models were found to be equivalent, in the sense that they allow exactly the same computations to be carried out. Other models were shown to be less powerful, but simpler to implement, and so useful for some purposes.
Synopsis
Part 1: Automata
 General introduction. Deterministic finite automata. Transition diagrams.
 Nondeterministic finite automata. The subset construction. Reduction of NFAs to DFAs.
 Regular Languages. Closure properties.
 Regular expressions.
 Compiling regular expressions into NFAs, and vice versa.
 Limits to NFAs. The Pumping Lemma. The MyhillNerode Theorem.
 Contextfree Languages and pushdown automata.
Part 2: Turing machines and computability
 Turing's analysis of computation. The Turing machine.
 The intuitive notion of computability. Decision problems. Encoding problems as sets of strings.
 Expressive power of Turing machines. Church's thesis.
 Undecidable problems. Diagonalization. The halting problem.
 Survey of decidable and undecidable problems.
 A glimpse beyond: computatonal complexity, P=NP?
 NPcompleteness
Syllabus
The finitestate machine. Deterministic finite automata and regular languarges.
Nondeterministic finite automata, and equivalence with DFA. Closure properties of regular languages.
Regular expressions.
The pumping lemma. The MyhillNerode Theorem.
Contextfree grammars. Pushdown automata.
The Turing machine. Church's Thesis. Decision problems and undecidability. The halting problem.
Reading list
Primary Texts
 M. Sipser, Introduction to the Theory of Computation (SouthWestern College Publishing, International 3rd Ed., 2012).
 D. C. Kozen, Automata and Computability (Springer, Reprint of 1st Ed., 2013).
Other suggestions
 J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages and Computation (AddisonWesley, 2nd Ed., 2001).