ÅÝܽ¶ÌÊÓƵ

School of Engineering and Informatics (for staff and students)

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

TypeTimingWeighting
Computer Based ExamSemester 2 Assessment50.00%
Coursework50.00%
Coursework components. Weighted as shown below.
TestT2 Week 11 (40 minutes)40.00%
Problem SetT2 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.

TermMethodDurationWeek pattern
Spring SemesterLecture1 hour22222222222
Spring SemesterSeminar1 hour01111111111

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.

School of Engineering and Informatics (for staff and students)

School Office:
School of Engineering and Informatics, ÅÝܽ¶ÌÊÓƵ, Chichester 1 Room 002, Falmer, Brighton, BN1 9QJ
ei@sussex.ac.uk
T 01273 (67) 8195

School Office opening hours: School Office open Monday – Friday 09:00-15:00, phone lines open Monday-Friday 09:00-17:00
School Office location [PDF 1.74MB]