- 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 (2012)

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

MODULE CODE | ECM3422 | MODULE CONVENER | Unknown |

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

DURATION: WEEKS | 11 weeks |

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

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 (e.g., to find the shortest round tour of 30 cities requires a computation which would take even the fastest computers longer than the age of the universe). 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).

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

**Module Specific Skills:**

- manipulate formal languages and create abstract automata to a given specification
- explain what is meant by a general model of computation and work with some specific examples of such models
- describe the mathematical basis of the theory of computability
- appreciate the relationship between the theory of computation and practical computing

**Discipline Specific Skills:**

- appreciate the power of abstraction to support a general understanding of some subject matter
- appreciate the role of theoretical understanding in underpinning disciplined and responsible practice

**Personal and Key Skills: **

- approach problems analytically at an appropriate level of abstraction

Formal Languages: Regular languages and regular expressions, context-free languages and grammars, pumping lemmas and other methods of proof. Automata: Finite-state automata, elimination of non-determinism, Kleene's theorem, push-down automata, Turing machines, the Universal Turing Machine. Computability: Recursive insolubility of the halting problem for Turing machines, the Church-Turing thesis and its variants, other models of computation the quest for hypercomputation. Complexity: Polynomial and exponential algorithms, the satisfiability problem and NP-completeness, the P vs NP problem.

Scheduled Learning & Teaching Activities | 34.00 | Guided Independent Study | 116.00 | Placement / Study Abroad |
---|

Category | Hours of study time | Description |

Scheduled Learning & Teaching | 22 | Lectures |

Scheduled Learning & Teaching | 12 | Tutorials |

Guided Independent Study | 30 | Coursework |

Guided Independent Study | 86 | Independent study |

Form of Assessment | Size of Assessment (e.g. duration/length) | ILOs Assessed | Feedback Method |
---|---|---|---|

Class test | 1 hour | 1, 2 | In class |

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

Form of Assessment | % of Credit | Size of Assessment (e.g. duration/length) | ILOs Assessed | Feedback Method |
---|---|---|---|---|

Written exam – closed book | 80 | 2 hours | 2, 3, 4, 5, 6, 7 | None |

Coursework – assignment 1 | 10 | 10 hours | 1, 2, 7 | Written |

Coursework – assignment 2 | 10 | 10 hours | 1, 2, 7 | Written |

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

All above | Written exam (100%) | All | Last week August |

Referred and deferred assessment will normally be by examination. For referrals, only the examination will count, a mark of 40% being awarded if the examination is passed. For deferrals, candidates will be awarded the higher of the deferred examination mark or the deferred examination mark combined with the original coursework mark.

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

ELE-http;//vle.exeter.ac.uk

Reading list for this module:

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

Set | Martin, John C. | Introduction to Languages and the Theory of Computation | McGraw-Hill | 2003 | [Library] | ||

Set | Parkes, Alan P | A Concise Introduction to Languages and Mechanics | Springer Verlag | 2008 | 978-1-84800-120-6 | [Library] |

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

PRE-REQUISITE MODULES | ECM1707 |
---|---|

CO-REQUISITE MODULES |

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

ORIGIN DATE | Monday 12 March 2012 | LAST REVISION DATE | Tuesday 26 November 2013 |

KEY WORDS SEARCH | Formal languages, automata, Turing Machine, computability, computational complexity |
---|