(Last Updated:03 May 2017)

**Total Credits: **10

**Level: **Level 3

**Target Students: **Third year undergraduate students in the School of Computer Science, in the School of Mathematics and other students who fulfil the pre-requisites. * Available to JYA/Erasmus students.*

**Taught Semesters:**

Semester | Assessment |
---|---|

Spring | Assessed by end of Spring Semester |

**Prerequisites: **None.

**Corequisites: **None.

**Summary of Content: **This module is concerned with the concept of a mechanical process. It begins by looking at some of the attempts to characterise the problems that can theoretically be solved by a computer. It then looks at some undecidable problems. These are problems for which it is impossible to construct a computer program. Finally the module considers the area of complexity theory. This field looks at whether or not computable problems can be computed in a reasonable time.

**Module Web Links:**

**Method and Frequency of Class: **

Activity | Number Of Weeks | Number of sessions | Duration of a session |
---|---|---|---|

Lecture | 12 weeks | 2 per week | 1 hour |

Activities may take place every teaching week of the Semester or only in specified weeks. It is usually specified above if an activity only takes place in some weeks of a Semester

**Method of Assessment: **

Assessment Type | Weight | Requirements |
---|---|---|

Exam 1 | 100 | 2 hr written examination |

**Convenor: **

Dr A Parkes

**Education Aims: **The overall aim of the course is to provide an understanding of the concept of computability. In particular, course objectives are:
To provide an appreciation of the many attempts that have been made to define the class of computable functions and also to indicate that all the sensible attempts to do this have been shown to be equivalent. To introduce the fact that there are problems that cannot possibly be solved on a computer.
To show how, apparently different, computable problems are related in respect of their algorithmic complexity.

**Learning Outcomes: ****Knowledge and Understanding**
understand the theory of programming via mathematical methods.
**Intellectual Skills**
apply and deploy mathematical ability, practices and tools,
understand and logically evaluate the problems in computability,
think independently about the issues while giving due weight to previous work,
understand the complex ideas of the theory of programming and relate them to particular problems.
**Professional Skills**
extend their own abilities by specialising or generalising from their previous knowledge
**Transferable Skills**
the ability to solve problems using mathematics, by consulting external sources if necessary.

**Offering School: **Computer Science

Use the **Back** facility of your browser to return to the previous page.

Return to The University of Nottingham Welcome Page