Computability and Intractability

Here are links to the course home page and the formal TQA description.

Description

The course centres around the so-called Church-Turing Thesis which proposes that each one of a variety of different formal systems adequately captures the intuitive concept of (effective) computability. This thesis implies that by studying any one of these systems, for example Turing machines, we can learn about the inherent theoretical limitations of computers. If a problem cannot be solved by a Turing machine, then there is no computable solution to it at all.

Not all the computational problems which can be solved in principle can be solved in practice: the computational resources required (time or space) may be prohibitive. This observation motivates the study of resource-bounded computation. Having accepted an extended version of the Church-Turing thesis--that the computationally tractable problems are those which can be efficiently solved by a Turing machine--we are led inevitably to conclude the existence of natural problems which can be solved in principle but not within any reasonable resource bound.

The fundamental concepts and techniques encountered in this course resonate around the whole of Computer Science and indeed beyond: effective procedures and decidability, simulation methods, machine encodings and universality, diagonalization arguments, and reductions between problems.

Syllabus

Finite state machines

Brief reminder of a model which does not encompass the intuitive notion of effective procedure.

Turing machines

Definition; some programming techniques and example machines; variants of the Turing machine and their equivalence.

The Church-Turing Thesis

Empirical evidence for the Thesis; equivalence of Turing machines to other models of computation, both simpler (two-register machines) and more complex (models of computation which are akin to real computers). Overview of the basic ideas; proofs are supplied in appendices to the course notes.

Universal machines

Encoding Turing machines; a universal Turing machine.

Decidability and partial decidability

The Halting Problem; reductions between problems.

Nondeterministic Turing machines

Definition and equivalence to deterministic machines.

Resource bounded computation

The class P and its interpretation as the class of computationally tractable decision problems; the class NP and its interpretation as the class of search problems with efficiently verifiable solutions.

NP-completeness

Cook's theorem; examples of problems which are complete for NP.

Connections with Logic

Brief introduction to first order and second order Logic and discussion of how the ideas relate to complexity classes, mainly the NP-complete problems.

Assessed Coursework

Three sets of assessed problem sets with solutions due in weeks 4, 7, and 10. The problem sets will be handed out in weeks 1, 4 and 7. Marked solutions to problem sets will be returned according to the following schedule: problem set 1 by week 6, problem set 2 by week 9 and problem set 3 at the beginning of the final examination block.

References:

* Ch. H. Papadimitriou Computational Complexity, Addison-Wesley 1994. Useful for those who intend to progress to the CS4 Computational Complexity course. Includes good discussion of Logic and its connections to computability. Also useful for those who intend to progress to the CS4 Computational Complexity course.

* J. E. Hopcroft and J. D. Ullman Introduction to Automata Theory, Languages and Computation, Addison-Wesley 1979.

* M. Minsky Computation: Finite and Infinite Machines, Prentice-Hall 1972. An excellent book and strong on motivation. Unfortunately, it is now only available as an expensive hardback. There are some copies in the reserve section of the JCMB library.

* M. R. Garey and D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman. A classic book, again strong on motivation covering the latter parts of the course.