next up previous contents
Next: Computer Graphics and Image Up: Lent Term 2003: Part Previous: Complexity Theory   Contents


Computation Theory

Lecturer: Prof. 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., Motwani, R. & Ullman, J.D. (2001). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2nd ed.).



next up previous contents
Next: Computer Graphics and Image Up: Lent Term 2003: Part Previous: Complexity Theory   Contents
Christine Northeast
Wed Sep 4 14:43:05 BST 2002