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.