Computing

Limits of Computation

Module code: G5029
Level 6
15 credits in spring teaching
Teaching method: Lecture, Seminar
Assessment modes: Coursework, Unseen examination

This module is all about fundamental questions like 'what is computable?' and 'what is feasibly computable?'. The following topics are covered: what is a universal program? What is program specialisation? (partial evaluation, also known as s-m-n theorem). What is self-application? (boot-strapping). How can it be used to speed-up programs? How can an unsolvable problem be defined using WHILE? How can this be generalised? (Rice's theorem). Are there decidable but unfeasible problems? What are typical examples? What does feasible mean? How can one measure resource-usage of (time, space, non-determinism) of WHILE programs? What are asymptotic complexity classes and what are their limitations? What do we know about existence of optimal solutions?

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