Computation Theory

Lecturer: Dr J.K.M. Moody

No. of lectures: 12

This course is a prerequisite for Complexity Theory, Quantum Computing (Part II).

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. 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 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. [1 lecture]

• Turing machines. Definition and examples. Searching states. Recognising well-matched bracketing. Representing natural numbers, unary. Doing arithmetic. [1 lecture]

• 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. [1 lecture]

• 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. [1 lecture]

• Undecidability of the halting problem. Statement and proof. The zero-input halting problem. The uniform halting problem. Existential definition of a non-computable function. [1 lecture]

• 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. [1 lecture]

• 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. [1 lecture]

• 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. [1 lecture]

• 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. [2 lectures]

• 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. [1 lecture]

• Undecidability. Confirming an answer is weaker than deciding a question. Some undecidable problems in recursive function theory. Applications to practical problems in computing. [1 lecture]

Objectives

At the end of the course students should

• believe that Turing's model is a plausible representation of single-threaded discrete computation

• understand the notion of coding programs as data, and of a universal machine

• 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. Addison-Wesley.
Hopcroft, J.E., Motwani, R. & Ullman, J.D. (2001). Introduction to automata theory, languages and computation. Addison-Wesley (2nd ed.).
Sudkamp, T.A. (1995). Languages and machines. Addison-Wesley (2nd ed.).
Jones, N.D. (1997). Computability and complexity. MIT Press. Kurki-Suonio, R. (1971). Computability and formal languages. Auerbach. out of print