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