Limits of Computation (G5029)
Limits of Computation
Module G5029
Module details for 2024/25.
15 credits
FHEQ Level 6
Pre-Requisite
Introduction to Programming, Program Analysis, Mathematical Concepts, Programming Concepts
Module Outline
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 students 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.
Library
Neil D Jones. Computability and Complexity from a Programming Perspective, MIT Press 1997.
J E Hopcraft, R Motwani, J D Ullman. Introduction to Automata Theory, Languages, and Computation, 2nd edition, Addison Wesley, 2001.
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).
| Type | Timing | Weighting |
|---|---|---|
| Computer Based Exam | Semester 2 Assessment | 50.00% |
| Coursework | 50.00% | |
| Coursework components. Weighted as shown below. | ||
| Test | T2 Week 11 (40 minutes) | 40.00% |
| Problem Set | T2 Week 6 | 60.00% |
Timing
Submission deadlines may vary for different types of assignment/groups of students.
Weighting
Coursework components (if listed) total 100% of the overall coursework weighting value.
| Term | Method | Duration | Week pattern |
|---|---|---|---|
| Spring Semester | Lecture | 1 hour | 22222222222 |
| Spring Semester | Seminar | 1 hour | 01111111111 |
How to read the week pattern
The numbers indicate the weeks of the term and how many events take place each week.
Prof Bernhard Reus
Assess convenor
/profiles/115097
Please note that the University will use all reasonable endeavours to deliver courses and modules in accordance with the descriptions set out here. However, the University keeps its courses and modules under review with the aim of enhancing quality. Some changes may therefore be made to the form or content of courses or modules shown as part of the normal process of curriculum management.
The University reserves the right to make changes to the contents or methods of delivery of, or to discontinue, merge or combine modules, if such action is reasonably considered necessary by the University. If there are not sufficient student numbers to make a module viable, the University reserves the right to cancel such a module. If the University withdraws or discontinues a module, it will use its reasonable endeavours to provide a suitable alternative module.