C&I Bibliography
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,
1980.
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,
1991.
Gives the indepth story of the connections between
Complexity and Logic. Not an easy read.

M.R. Garey and D. S. Johnson, Computers
and Intractability: A Guide to the Theory of NPCompleteness, Freeman,
1979.
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 NPcompletenes.

J.E. Hopcroft and J.D. Ullman,
Introduction to Automata Theory, Languages and Computation, AddisonWesley
1979.
Contains material relevant ot this module.
Also proves lower bounds for various problems (e.g., ones connected with
regular expressions).

M. Minsky,
Computation: Finite and Infinite Machines, PrenticeHall 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.

Ch.H. Papadimitriou,
Computational Complexity, AddisonWesley 1994.
Useful for those who intend to progress to the CS4 Computational Complexity
module. Includes good discussion of Logic and its connections
to computability. An excellent introduciton to most of the concerns
of modern day complexity.

H. Rogers, Jr., Theory of Recursive
Functions and Effective Computability, McGrawHill, 1967.
The bible of pure computability theory.
One for the truly dedicated, but highly readable. Predates the material
of the second part of the course.