Limits of Computation (G5029)

15 credits, Level 6

Spring teaching

This module addresses fundamental questions of computing like 'what is computable?' and 'what is feasibly computable?' The problems are discussed using a particular choice of 'effective procedure' that you can program in easily. This allows one to view all problems and solutions in this course as programming-related.

The importance of understanding the reasons for the existence of non-computable and intractable problems is discussed, techniques for recognising them are presented and real-world examples of non-computable or intractable problems are given.

The following topics are covered to answer the fundamental questions above:

  • Interpreters, compilers, specializers, in particular self-interpreters.
  • Definition of an unsolvable problem (Halting problem) and generalisation (Rice's Theorem).
  • Examples of unsolvable problems.
  • What does feasible mean? How can one measure resource-usage of (time, space, non-determinism) of programs?
  • Definition of unfeasible problems. Examples of such problems.
  • Definition of asymptotic complexity classes and their relationships.

Teaching

69%: Lecture
31%: Seminar

Assessment

50%: Coursework (Problem set, Test)
50%: Examination (Computer-based examination)

Contact hours and workload

This module is approximately 150 hours of work. This breaks down into about 32 hours of contact time and about 118 hours of independent study. The 5X社区视频 may make minor variations to the contact hours for operational reasons, including timetabling requirements.

We regularly review our modules to incorporate student feedback, staff expertise, as well as the latest research and teaching methodology. We鈥檙e planning to run these modules in the academic year 2024/25. However, there may be changes to these modules in response to feedback, staff availability, student demand or updates to our curriculum.

We鈥檒l make sure to let you know of any material changes to modules at the earliest opportunity.