Catalogue of Modules, University of Nottingham

G53COM Computability
(Last Updated:03 May 2017)

Year  09/10

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:

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:
  • Reading List
  • Method and Frequency of Class:

    ActivityNumber Of WeeksNumber of sessionsDuration of a session
    Lecture 12 weeks2 per week1 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 TypeWeightRequirements
    Exam 1 100 2 hr written examination 

    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.

    Module Catalogue Search for another module

    [UoN Welcome Page] Return to The University of Nottingham Welcome Page