This is short list of books that relate
to the module. Although notes are supplied, it is a good idea
to browse through related material, either to get an alternative point
of view or to see how much more there is to the subject.
N.J. Cutland, Computability, Cambridge University Press,
This covers the first part of the course (to
much more depth). Uses RAMs as the basic model.
H.-D. Ebbinghaus and J. Flum, Finite
Model Theory, Perspectives in Mathematical Logic, Springer,
Gives the in-depth story of the connections between
Complexity and Logic. Not an easy read.
H. Rogers, Jr., Theory of Recursive
Functions and Effective Computability, McGraw-Hill, 1967.
M.R. Garey and D. S. Johnson, Computers
and Intractability: A Guide to the Theory of NP-Completeness, Freeman,
A classic book, strong on motivation covering
the latter parts of the module. A must for those who want to know
more as well as the origins of many of the results and ideas.
A. Gibbons, Algorithmic
Graph Theory, Cambridge University Press.
A book on graph theory from the algorithmic point
of view. Contains material on NP-completenes.
J.E. Hopcroft and J.D. Ullman,
Introduction to Automata Theory, Languages and Computation, Addison-Wesley
Contains material relevant ot this module.
Also proves lower bounds for various problems (e.g., ones connected with
Computation: Finite and Infinite Machines, Prentice-Hall 1972.
An excellent book and strong on motivation.
Unfortunately, it is now only available as an expensive hardback. There
are some copies in the reserve section of the JCMB library.
Computational Complexity, Addison-Wesley 1994.
Includes good discussion of Logic and its connections
to computability. An excellent introduciton to most of the concerns
of modern day complexity.
Useful for those who intend to progress to the CS4 Computational Complexity
The bible of pure computability theory.
One for the truly dedicated, but highly readable. Predates the material
of the second part of the course.