next up previous contents
Next: Digital Communication Up: Lent Term 2002: Part Previous: Compiler Construction   Contents

Computation Theory

Lecturer: Dr A.M. Pitts (amp12@cl.cam.ac.uk)

No. of lectures: 12

This course is a prerequisite for Complexity Theory.


Aims


The aim of this course is to introduce several apparently different formalisations of the informal notion of algorithm; to show that they are equivalent; and to use them to demonstrate that there are uncomputable functions and algorithmically undecidable problems.


Lectures

Objectives


At the end of the course students should

Recommended books


Davis, M.D., Sigal, R. & Wyuker E.J. (1994). Computability, Complexity and Languages. Academic Press (2nd ed.).
Sudkamp, T.A. (1995). Languages and Machines. Addison-Wesley (2nd ed.).
Jones, N.D. (1997). Computability and Complexity. MIT Press.
Hopcroft, J.E. & Ullman, J.D. (1979). Introduction to Automata Theory, Languages and Computation. Addison-Wesley.



next up previous contents
Next: Digital Communication Up: Lent Term 2002: Part Previous: Compiler Construction   Contents
Christine Northeast
Tue Sep 4 09:34:31 BST 2001