Computing

Limits of Computation

Module code: G5029
Level 6
15 credits in spring semester
Teaching method: Lecture, Seminar
Assessment modes: Computer based exam, Coursework

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.

Pre-requisite

Introduction to Programming, Program Analysis, Mathematical Concepts, Programming Concepts

Module learning outcomes

  • Have systematic understanding of the limitations of computing devices in the sense of what is computable and what is feasible (including the key concepts of semi-decidability and decidability, and equivalence of different notions of computability).
  • Have the ability to deploy established techniques to identify unfeasible problems.
  • Have systematic understanding of different complexity classes and the ability to deploy established techniques to assign problems to those complexity classes.
  • Understand and explain several classic results of complexity theory with an appreciation for the uncertainty of P=NP and the impact on practical (every day) programming (problems).