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


Computation Theory

Lecturer: Dr J.K.M. Moody

No. of lectures: 12

This course is a prerequisite for Complexity Theory, Quantum Computing (Part II).


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. The course approach is essentially that of programming, and a Universal register machine is constructed which acts as an interpreter on explicit codings of algorithm and data. These explicit codings are exploited to show that the Halting Problem is not decidable, and that there are sets which can be listed but whose membership cannot be checked.


Lectures

Objectives


At the end of the course students should

Recommended books


Brookshear, J.G. (1989). Theory of computation: formal languages, automata, and complexity. Addison-Wesley.
Hopcroft, J.E., Motwani, R. & Ullman, J.D. (2001). Introduction to automata theory, languages and computation. Addison-Wesley (2nd ed.).
Sudkamp, T.A. (1995). Languages and machines. Addison-Wesley (2nd ed.).
Jones, N.D. (1997). Computability and complexity. MIT Press.
Kurki-Suonio, R. (1971). Computability and formal languages. Auerbach. out of print



next up previous contents
Next: Computer Graphics and Image Up: Lent Term 2004: Part Previous: Complexity Theory   Contents
Christine Northeast
Thu Sep 4 15:29:01 BST 2003