Skip to main content

Study information

Computability and Complexity - 2025 entry

MODULE TITLEComputability and Complexity CREDIT VALUE15
MODULE CODEECM3422 MODULE CONVENERProf Achim D. Brucker (Coordinator), Diego Marmsoler (Coordinator)
DURATION: TERM 1 2 3
DURATION: WEEKS 11 weeks 0 0
Number of Students Taking Module (anticipated) 40
DESCRIPTION - summary of the module content

It is popularly supposed that there is no limit to the power of computers to perform any task, so long as it is sufficiently well defined, and to do so quickly and efficiently. In fact this is not so, and it can be proved mathematically that there are well-defined computational tasks which cannot, in principle, be performed by computers as we know them; and other tasks which, while they can be performed, cannot be completed in a feasible amount of time. This module will introduce you to the Turing Machine model of computation which underpins the fundamental theories of computability (concerned with what can be computed at all) and complexity (concerned with how efficiently things which can be computed can be computed). These theories will be introduced in a precise and formal way, and the main results and theorems will be stated and proven.

AIMS - intentions of the module

To introduce the Mathematical basis and practical implications of the classical theory of computability and complexity and to consider the extent to which this is still relevant to modern developments in computing.

INTENDED LEARNING OUTCOMES (ILOs) (see assessment section below for how ILOs will be assessed)

On successful completion of this module, you should be able to:

Module Specific Skills and Knowledge:

  1. Explain what is meant by a general model of computation and work with some specific examples of such models;

  2. Describe the mathematical basis of the theory of computability and complexity;

  3. Appreciate the relationship between the theory of computation and complexity and practical computing.

Discipline Specific Skills and Knowledge:

  1. Appreciate the power of abstraction to support a general understanding of some subject matter;

  2. Appreciate the role of theoretical understanding in underpinning disciplined and responsible practice.

Personal and Key Transferable / Employment Skills and Knowledge:

  1. Approach problems analytically at an appropriate level of abstraction.

SYLLABUS PLAN - summary of the structure and academic content of the module
  • Turing machines, and the universal Turing machine;

  • Recursive and recursively enumerable languages;

  • Undecidability of the halting problem for Turing machines; variants of the halting problem; other undecidable languages;

  • The Church-Turing thesis;

  • Properties of languages and Rice’s theorem;

  • Time complexity;

  • Complexity classes P and NP, and the P vs NP problem;

  • NP-complete problems;

  • Cook’s theorem;

  • Space complexity classes and their relationships with the other complexity classes seen in the module

LEARNING AND TEACHING
LEARNING ACTIVITIES AND TEACHING METHODS (given in hours of study time)
Scheduled Learning & Teaching Activities 46 Guided Independent Study 104 Placement / Study Abroad 0
DETAILS OF LEARNING ACTIVITIES AND TEACHING METHODS

 

Category

Hours of study time

Description

Scheduled learning and teaching activities

22

Lectures

Scheduled learning and teaching activities

24

Tutorials

Guided independent study

24

Coursework

Guided independent study

80

Independent study

 

ASSESSMENT
FORMATIVE ASSESSMENT - for feedback and development purposes; does not count towards module grade

Not applicable.

SUMMATIVE ASSESSMENT (% of credit)
Coursework 20 Written Exams 80 Practical Exams 0
DETAILS OF SUMMATIVE ASSESSMENT

Form of Assessment

% of Credit

Size of Assessment (e.g. duration/length)

ILOs Assessed

Feedback Method

Written exam – closed book

80

2 hours - Summer Exam Period

1-6

Written

Coursework assignment

20

20 hours

1, 2, 4, 5, 6

Written

 

DETAILS OF RE-ASSESSMENT (where required by referral or deferral)

Original Form of Assessment

Form of Re-assessment

ILOs Re-assessed

Time Scale for Re-reassessment

Written Exam

Written Exam (2 hours, 80%)

1-6

Referral/deferral period

Coursework Assignment

Coursework Assignment (20 hours, 20%)

1, 2, 4, 5, 6

Referral/deferral period

 

RE-ASSESSMENT NOTES

Reassessment will be by coursework and/or written exam in the failed or deferred element only. For referred candidates, the module mark will be capped at 40%. For deferred candidates, the module mark will be uncapped.

RESOURCES
INDICATIVE LEARNING RESOURCES - The following list is offered as an indication of the type & level of
information that you are expected to consult. Further guidance will be provided by the Module Convener

Author

Title

Edition

Publisher

Year

ISBN

Hopcroft, J. E.; Motwani, R. and Ullman, J. D.

Introduction to Automata Theory, Languages, and Computation 

3

Addison-Wesley

2007

978-0321476173

Michael Sipser

Introduction to the theory of computation

3

Cengage Learning

2013

9781473703186

  • ELE

Reading list for this module:

Type Author Title Edition Publisher Year ISBN
Set Hopcroft, J. E.; Motwani, R. and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation 3 Addison-Wesley 2007 978-0321476173
CREDIT VALUE 15 ECTS VALUE 7.5
PRE-REQUISITE MODULES ECM1415, MTH1001
CO-REQUISITE MODULES
NQF LEVEL (FHEQ) 3 (NQF level 6) AVAILABLE AS DISTANCE LEARNING No
ORIGIN DATE Thursday 6th July 2017 LAST REVISION DATE Wednesday 2nd April 2025
KEY WORDS SEARCH Turing machine; computability; computational complexity.

Please note that all modules are subject to change, please get in touch if you have any questions about this module.