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
- Introduction: algorithmically undecidable problems.
Decision problems. The informal notion of algorithm, or effective
procedure. Examples of algorithmically undecidable problems. [1
lecture]
- Register machines. Definition and examples; graphical
notation. Register machine computable functions. Doing arithmetic
with register machines. [1 lecture]
- Universal register machine. Natural number encoding of
pairs and lists. Coding register machine programs as numbers.
Specification and implementation of a universal register machine. [2
lectures]
- Undecidability of the halting problem. Statement and
proof. Example of an uncomputable partial function. Decidable sets
of numbers; examples of undecidable sets of numbers. [1 lecture]
- Turing machines. Informal description. Definition and
examples. Turing computable functions. Equivalence of register
machine computability and Turing computability. The Church-Turing
Thesis. [2 lectures]
- Primitive recursive functions. Definition and examples.
Primitive recursive partial function are computable and total.
[1 lecture]
- Partial recursive functions. Definition. Existence of a
recursive, but not primitive recursive function. Ackermann's
function. A partial function is partial recursive if and only if it
is computable. [2 lectures]
- Recursive and recursively enumerable sets. Decidability and
recursive sets. Generability and recursive enumeration. Example of
a set that is not recursively enumerable. Example of a recursively
enumerable set that is not recursive. Alternative characterisations
of recursively enumerable sets as the images and the domains of
definition of partial recursive functions. [2 lectures]
Objectives
At the end of the course students should
- be familiar with the register machine and Turing machine models
of computability
- understand the notion of coding programs as data, and of a universal
machine
- be able to use diagonalisation to prove the undecidability of
the Halting Problem
- understand the mathematical notion of partial recursive function
and its relationship to computability
- be able to develop simple mathematical arguments to show that
particular sets are not recursively enumerable
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: Computer Graphics and Image
Up: Lent Term 2003: Part
Previous: Complexity Theory
  Contents
Christine Northeast
Wed Sep 4 14:43:05 BST 2002