Next: Computer Graphics and Image
Up: Lent Term 2001: Part
Previous: Compiler Construction
Lecturer: Dr J.K.M. Moody
(km@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 the mathematical theory of
discrete sequential computation, initially through Turing machines.
The essentials of the model are that there is a fixed finite
presentation of the algorithm but unlimited working space, with
termination signalled by a data dependent stopping rule. 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 further 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
- The nature of computation.
Formal systems. Modelling the process of proof within arithmetic.
Godel's Incompleteness Theorem (informal). Decision problems. The
informal notion of algorithm, or effective procedure. Some formal
models of computation. What they have in common. Turing's thesis.
- Turing machines.
Definition and examples. Searching states. Recognising well-matched
bracketing. Representing natural numbers, unary. Doing arithmetic.
- Register machines.
Definition and examples. Unary arithmetic (stack counters).
Natural number encoding of pairs and lists. 2-register machines.
Coding general programs. Register machine configurations.
- Universal register machine.
Specifying a register machine computation by integer codes (p, d).
Estimate of the code for a multiplier program. Enumerating programs.
Building an interpreter. Handling exceptions.
- Undecidability of the halting problem.
Statement and proof. The zero-input halting problem. The uniform
halting problem. Existential definition of a non-computable function.
- Equivalent computations.
Turing machine configurations. Simulation of a Turing machine by a
register machine. Simulation of a 2-register machine by 2-state and
2-symbol Turing machines. Mention of Markov algorithms.
- Recursive functions.
Church's thesis. Peano's definition of the natural numbers.
Recursive function definition as a scheme of computation. Primitive
recursive functions: they are Total. Partial recursive functions.
Total recursive functions. Ackermann's function.
- Computable functions.
Computing partial recursive functions on a register machine. Godel
numbering of Turing machine configurations. Recursive description of
Turing machine computation. The equivalence of Church's thesis and
Turing's thesis. Representing a register machine program by its
Godel number. A universal partial recursive function.
- Recursive enumeration.
Decidability and recursive sets. Generability and recursive enumeration.
Basic properties. The idea of a non-constructible proof. Examples:
the set of all finite sets, the set of all recursive sets. Enumerating
sets of functions using their Godel numbers. Any enumeration of a set
of total recursive functions can be extended.
- Parallel evaluation.
Recursive bags. Step-by-step computation of a partial recursive function.
Its evaluation for all arguments in parallel. A non-empty set is the
range of a total recursive function if and only if it is the domain of a
partial recursive function.
- Undecidability.
Confirming an answer is weaker than deciding a question. Some undecidable
problems in recursive function theory. Applications to practical problems
in computing.
Objectives
At the end of the course students should
- believe that Turing's model is a plausible representation of
single-threaded discrete computation
- enjoy programming simple algorithms on both Turing and register
machines
- understand how to model and check simple recursive function
definitions using ML
- be able to develop simple mathematical arguments to show that
particular sets are not recursively enumerable
Recommended books
Brookshear, J.G. (1989). Theory of Computation: Formal Languages,
Automata, and Complexity. Benjamin/Cummings.
Kurki-Suonio, R. (1971). Computability and Formal Languages.
Auerbach.
Hopcroft, J.E. & Ullman, J.D. (1979). Introduction to Automata
Theory, Languages and Computation. Addison-Wesley.
Sudkamp, T.A. (1988). Languages and Machines. Addison-Wesley.
Jones, N.D. (1997). Computability and Complexity. MIT Press.
Next: Computer Graphics and Image
Up: Lent Term 2001: Part
Previous: Compiler Construction
Christine Northeast
Wed Sep 20 15:13:44 BST 2000