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.

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

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.