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).

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.

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.