Computation Theory

Lecturer: Dr J.K.M. Moody (km@cl.cam.ac.uk)

No. of lectures: 12

This course is a prerequisite for Complexity Theory (Part IB).

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.