- Homepage
- Key Information
- Students
- Taught programmes (UG / PGT)
- Student Services and Procedures
- Student Support
- Events and Colloquia
- International Students
- Students as Change Agents (SACA)
- Student Staff Liaison Committees (SSLC)
- The Exeter Award
- Peer Support
- Skills Development
- Equality and Diversity
- Athena SWAN
- Outreach
- Living Systems Institute Webpage
- Alumni
- Info points and hubs
- Inbound Exchange Students

- Staff
- PGR
- Health and Safety
- Computer Support
- National Student Survey (NSS)
- Intranet Help
- College Website

## ECM3422 - Computability and Complexity (2023)

MODULE TITLE | Computability and Complexity | CREDIT VALUE | 15 |
---|---|---|---|

MODULE CODE | ECM3422 | MODULE CONVENER | Guoqiang Zhang (Coordinator) |

DURATION: TERM | 1 | 2 | 3 |
---|---|---|---|

DURATION: WEEKS | 11 weeks | 0 | 0 |

Number of Students Taking Module (anticipated) | 40 |
---|

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.

Pre-requisites: ECM1414, ECM2418

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.

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:**

4 appreciate the power of abstraction to support a general understanding of some subject matter;

5 appreciate the role of theoretical understanding in underpinning disciplined and responsible practice.

**Personal and Key Transferable / Employment Skills and Knowledge**:

6 approach problems analytically at an appropriate level of abstraction.

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

Scheduled Learning & Teaching Activities | 46.00 | Guided Independent Study | 104.00 | Placement / Study Abroad |
---|

Category | Hours of study time | Description |

Scheduled learning and teaching | 22 | Lectures |

Scheduled learning and teaching | 24 | Tutorials |

Guided Independent Study | 24 | Coursework |

Guided Independent Study | 80 | Independent study |

None.

Coursework | 20 | Written Exams | 80 | Practical Exams | 0 |
---|

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, 2, 3, 4, 5, 6 | None |

Coursework assignment | 20 | 20 hours | 1, 2, 4, 5, 6 | Written |

Original Form of Assessment | Form of Re-assessment | ILOs Re-assessed | Time Scale for Re-reassessment |
---|---|---|---|

Written Exam | Written Exam (2 hours) | All | August Ref/Def period |

Coursework Assignment | Coursework Assignment | 1, 2, 4, 5, 6 | August Ref/Def period |

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.

information that you are expected to consult. Further guidance will be provided by the Module Convener

ELE-https://vle.exeter.ac.uk

Reading list for this module:

Type | Author | Title | Edition | Publisher | Year | ISBN | Search |
---|---|---|---|---|---|---|---|

Set | Hopcroft, J. E.; Motwani, R. and Ullman, J. D. | Introduction to Automata Theory, Languages, and Computation | 3 | Addison-Wesley | 2007 | 978-0321476173 | [Library] |

CREDIT VALUE | 15 | ECTS VALUE | 7.5 |
---|---|---|---|

PRE-REQUISITE MODULES | ECM1414, ECM2418 |
---|---|

CO-REQUISITE MODULES |

NQF LEVEL (FHEQ) | 3 (NQF level 6) | AVAILABLE AS DISTANCE LEARNING | No |
---|---|---|---|

ORIGIN DATE | Thursday 06 July 2017 | LAST REVISION DATE | Wednesday 08 February 2023 |

KEY WORDS SEARCH | Turing machine; computability; computational complexity. |
---|