Computation Theory

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

No. of lectures: 12  

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. Recognizing 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. Recursive description of Turing machines. Representing a register machine program by its Godel number. The equivalence of Church's thesis and Turing's thesis. A universal partial recursive function.

Recursive enumeration.

Recursive and recursively enumerable sets. Examples: the set of all finite sets, the set of all recursive sets. Enumerating sets of functions using their Godel numbers. Any enumeration of total recursive functions can be extended. One or more examples from old Tripos papers.

Parallel evaluation.

Step-by-step computation of recursive functions. Parallel evaluation. The idea of a non-uniform proof. 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.

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.