The module 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 module 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.
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 Term 3.